Author |
Topic: 2^x (mod x) = 3 (Read 1298 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: 2^x (mod x) = 3
« Reply #1 on: Apr 13th, 2003, 10:39am » |
 Quote  Modify
|
Should I assume from the fact that you put this in the "Hard" section, that the trivial solution was unintended?
|
|
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 2^x (mod x) = 3
« Reply #3 on: Apr 13th, 2003, 11:22am » |
Quote Modify
|
Being that NickH has been known to put problems in the Easy section, that are tougher than many in the Hard section, I doubt if there is a trivial solution to this. I have a feeling x is going to be quite large. Icarus, what is the trivial solution you are thinking of? Are you thinking that the 3 is also evaluated mod x, and the solution is x=2?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^x (mod x) = 3
« Reply #4 on: Apr 13th, 2003, 1:53pm » |
Quote Modify
|
There can only be one answer, since the smallest positive one is requested..
I think it's infinity, but I wouldn't know how to proof it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #5 on: Apr 13th, 2003, 2:13pm » |
Quote Modify
|
I should confess here that, although I know the answer, I don't have a solution, other than brute force.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 2^x (mod x) = 3
« Reply #6 on: Apr 13th, 2003, 6:49pm » |
Quote Modify
|
What I was refering to is x=1: 2 = 3 mod 1. I suppose you could say that 2x (mod x) means the remainder (from 0 to x-1) when dividing by x. But this is not a standard notation that I have heard of, so I would say that it behooves you to more explicit in the statement. It would be better I think to state the congruence in the more usual form and restrict the problem to x > 1.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #7 on: Apr 14th, 2003, 7:21am » |
Quote Modify
|
NickH, can you confirm that the solution is greater than 300000? If not then I don't want to waste any more CPU time running my defective program. 
|
|
IP Logged |
|
|
|
visitor
Guest
|
I thought I found a solution using brute force, but when I tried to confirm it, I realized my program was using exponential notation for the power of 2 calculation and dropping some least significant digits in the process. Is harpanet's program really calculating the power of 2 to that many places? Are we sure Nick's program isn't making the same mistake mine did? (granted, I wasn't using the high-powered math programs you may have).
|
|
IP Logged |
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #9 on: Apr 14th, 2003, 8:50am » |
Quote Modify
|
I started off trying to find short-cuts to mods and powers and using language-provided functions but I kept coming across problems (either conceptual or loss of precision). So in the end I wrote a couple of C# routines that work on arrays of numbers.
I haven't proven that they are without bugs 'cos, as you say, the numbers get WAY big very quickly. Hence my question to NickH.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^x (mod x) = 3
« Reply #10 on: Apr 14th, 2003, 10:47am » |
Quote Modify
|
The answer is several orders of magnitude over 300 000, but there is one..
(I googled for it)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #11 on: Apr 14th, 2003, 10:49am » |
Quote Modify
|
harpanet, yes, the solution I have is quite a bit bigger than 300000.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #12 on: Apr 14th, 2003, 10:53am » |
Quote Modify
|
hmmmm. Several orders of magnitude? At the rate its slowing down (per power) it's gonna take a long old time. Currently I am processing powers of 2 with just under 200000 decimal digits.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #13 on: Apr 14th, 2003, 10:56am » |
Quote Modify
|
There are a few tricks that can be used to reduce the number of multiplications required...
For example, it's possible to verify that x = 1025 is not a solution in just a minute or two on the Windows calculator.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #14 on: Apr 14th, 2003, 1:24pm » |
Quote Modify
|
Machine crash @ about 800000 . Well I guess it gives me the chance to optimise it.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 2^x (mod x) = 3
« Reply #15 on: Apr 14th, 2003, 5:21pm » |
Quote Modify
|
You don't need to keep track of giant numbers, if you keep reducing mod x when it is appropriate. The modulus of 2x can be found with something like:
m=2; for(i=1;i<x;i++){ m*=2; if(m>x) m=m%x;}
For more speed you can do it in larger chunks. Instead of multipling by 2, x-1 times, multiply by some higher power of 2 fewer times.
Also, x must be an odd, non-prime number. If x were even the value mod x would be even. If x were prime then 2^x mod x would be 2. It is probably not worth checking for primeness, but only trying the odd x is easy.
|
|
IP Logged |
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #16 on: Apr 15th, 2003, 2:38am » |
Quote Modify
|
I'm already using pretty big chunks for calculating the mod (2^64), but I hadn't considered calculating it only for odd values of x (bit of a d'oh moment  ). Cheers.
Current attempt is much faster, reached x = 6,000,000 in under 11 hours (1 GHz PIII). Should be able to double its speed though.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2^x (mod x) = 3
« Reply #17 on: Apr 15th, 2003, 3:16am » |
Quote Modify
|
x also isn't devisable by three, if that helps..
(2^x isn't devisable by three, so 2^x - 3 = a*x also isn't devisable by three, so x isn't either)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #18 on: Apr 15th, 2003, 12:45pm » |
Quote Modify
|
This seems to have turned into a programming contest! Perhaps there is no simple analytical solution.
There are a few tricks, some mentioned above, that can be used to optimize a brute force check.
1) Calculate the binary representation of x to minimize the number of multiplications.
Example: 44 = 1011002.
Then 44 = 4 + 8 + 32.
So 244 = 24+8+32 = 24 * 28 * 232.
The powers of two can be calculated by successively squaring.
2) Use Euler's Theorem, which states that aphi(n) = 1 (mod n), where phi(n) is the number of positive integers less than n which are coprime to n. <added>We also need gcd(a,n) = 1, which will be true here since a = 2 and we are only testing odd n.</added>
Phi(n) is easy to calculate from the prime factorization of n. Phi(pr) = pr - pr-1, for prime p. Also, phi is a multiplicative function, so that phi(ab) = phi(a) * phi(b), if gcd(a,b) = 1. So phi(n) can be calculated by multiplying each phi(pr). Having done this, take n (mod phi(n)).
Nick
|
| « Last Edit: Apr 15th, 2003, 3:16pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #19 on: Apr 15th, 2003, 1:05pm » |
Quote Modify
|
Point 2 went somewhat over my head! I'll have to think about that one a bit more.
As far as calculating 2^x, I am simply bit shifting a 64 bit value 1 bit at a time and keeping a counter of how many sets of 64 I have done.
The part that's dragging the processing down is the modulus. I am using SWF's observation that the mod need be calculated only for odd x, so that cuts down the number of calculations by 50%.
I am also making some other optimisations that I am not sure about. Would I be correct to say the following:
if (a mod m) is even or (b mod m) is even then
(a . b^c mod m) must also be even?
In my case a is the upper 64 bits of my 2^x calculation while b is 2^64.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #20 on: Apr 15th, 2003, 1:43pm » |
Quote Modify
|
You should skip multiples of 3, too, as towr suggests.
Tip 1 that I mention, above, is the most significant optimization I can think of. It gives you an O(log n) rather than O(n) solution. Suppose you're checking x = 1,000,000,001. Rather than doing a billion multiplications (or 1 billion / 64), the tip will let you do around 30!
Quote:if (a mod m) is even or (b mod m) is even then
(a . b^c mod m) must also be even? |
|
If I'm understanding you correctly, this is not true. Try a = 2, b = 3, m = 5, c = 2.
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #21 on: Apr 15th, 2003, 1:56pm » |
Quote Modify
|
Quote:If I'm understanding you correctly, this is not true. Try a = 2, b = 3, m = 5, c = 2.
|
|
Gosh darn!
1,2,3,4...
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: 2^x (mod x) = 3
« Reply #22 on: Apr 18th, 2003, 5:37am » |
Quote Modify
|
Here are a couple of JavaScript functions I wrote to work on this puzzle. The program checks all integers from 5 to 1,000,000 that are not multiples of 2 or 3. It takes about 30 seconds to run on my 600MHz PC.
The program doesn't actually work if you try to extend it into the billions, because JavaScript doesn't store large enough integers to handle p*p or p*result, but it could be adapted to run in a language that does support large integers. (Java?)
Nick
function check(m) {
var n = (m - 1) / 2;
var result = 2, p = 2;
do {
p = (p * p) % m;
var r = n % 2;
if (r == 1) result = (p * result) % m;
n = (n - r) / 2;
} while (n != 0);
if (result == 3) document.write(m, "<br>");
}
function doIt() {
var d = 4;
for (var i = 5; i <= 1000000; i += d) {
check(i);
d = 6 - d;
}
document.write("Done");
}
|
| « Last Edit: Apr 18th, 2003, 10:28am by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: 2^x (mod x) = 3
« Reply #23 on: Apr 18th, 2003, 12:21pm » |
Quote Modify
|
NickH, I implemented your code in C# and it located the answer 4700063497 in 4 hours 40 minutes (1GHz PIII).
C# supports 64 bit unsigned integers (ulong), which works fine until you reach 2^32, then p*p (or p*result) might blow it (although after the mod has been applied it falls back to below 2^64). In these cases I temporarily (it is much slower) used a decimal type (28 decimal digits) for the multiplication and mod and then bunged it back into a ulong.
|
| « Last Edit: Apr 20th, 2003, 7:50am by harpanet » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove