wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 2^x (mod x) = 3
        
(Message started by: NickH on Apr 13^th, 2003, 2:49am)

Title: 2^x (mod x) = 3
Post by NickH on Apr 13^th, 2003, 2:49am

Find the smallest positive integer, x, such that 2^x (mod x) = 3.

Title: Re: 2^x (mod x) = 3
Post by Icarus on Apr 13^th, 2003, 10:39am

Should I assume from the fact that you put this in the "Hard" section, that the trivial solution was unintended?

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 13^th, 2003, 11:00am

What trivial solution is that?

Title: Re: 2^x (mod x) = 3
Post by SWF on Apr 13^th, 2003, 11:22am

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?

Title: Re: 2^x (mod x) = 3
Post by towr on Apr 13^th, 2003, 1:53pm

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..

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 13^th, 2003, 2:13pm

I should confess here that, although I know the answer, I don't have a solution, other than brute force.

Title: Re: 2^x (mod x) = 3
Post by Icarus on Apr 13^th, 2003, 6:49pm

What I was refering to is x=1: 2 = 3 mod 1. I suppose you could say that 2^x (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.

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 14^th, 2003, 7:21am

NickH, can you confirm that the solution is greater than [hide]300000[/hide]? If not then I don't want to waste any more CPU time running my defective program. >:(

Title: Re: 2^x (mod x) = 3
Post by visitor on Apr 14^th, 2003, 8:38am

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).

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 14^th, 2003, 8:50am

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.

Title: Re: 2^x (mod x) = 3
Post by towr on Apr 14^th, 2003, 10:47am

The answer is several orders of magnitude over 300 000, but there is one..
(I googled for it)

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 14^th, 2003, 10:49am

harpanet, yes, the solution I have is quite a bit bigger than 300000.

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 14^th, 2003, 10:53am

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.

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 14^th, 2003, 10:56am

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.

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 14^th, 2003, 1:24pm

Machine crash @ about 800000 >:( . Well I guess it gives me the chance to optimise it.

Title: Re: 2^x (mod x) = 3
Post by SWF on Apr 14^th, 2003, 5:21pm

You don't need to keep track of giant numbers, if you keep reducing mod x when it is appropriate. The modulus of 2^x 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.

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 15^th, 2003, 2:38am

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.

Title: Re: 2^x (mod x) = 3
Post by towr on Apr 15^th, 2003, 3:16am

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)

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 15^th, 2003, 12:45pm

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 = 101100₂.
Then 44 = 4 + 8 + 32.
So 2⁴⁴ = 2⁴⁺⁸⁺³² = 2⁴ * 2⁸ * 2³².
The powers of two can be calculated by successively squaring.

2) Use Euler's Theorem, which states that a^phi(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(p^r) = p^r - p^r-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(p^r). Having done this, take n (mod phi(n)).

Nick

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 15^th, 2003, 1:05pm

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.

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 15^th, 2003, 1:43pm

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

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 15^th, 2003, 1:56pm

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...

Title: Re: 2^x (mod x) = 3
Post by NickH on Apr 18^th, 2003, 5:37am

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");
}

Title: Re: 2^x (mod x) = 3
Post by harpanet on Apr 18^th, 2003, 12:21pm

NickH, I implemented your code in C# and it located the answer [hide]4700063497[/hide] 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.