# Convert an unsolved number theory problem into a shorter program?

This problem of Waring's is unsolved: For all $n \ge 2$, $\lfloor (\frac 32 ) ^n \rfloor + {3^n} \bmod{2^n} < 2^n$. (Kubina and Wunderlich have tested this up to $471,600,000$.) This can be converted into a "C-like" program:

x = 9;
y = 4;
while ( x/y + x%y < y ) {
x = 3*x;
y = 2*y;
}


which can be shortened slightly to:

x = 9;
for( y = 4 ; x/y + x%y < y ; y *= 2 )
x *= 3;


Does anyone know of an unsolved problem which can be converted into a shorter program? The program must halt iff the problem is false. Put differently, I conjecture that the above program is the shortest whose halting is unknown. I want the program to be C-like, with integers of unlimited size.

-
Lew knows about this, but others may benefit by perusing mathoverflow.net/questions/29949/… – Gerry Myerson Oct 11 '12 at 3:42

I conjecture that the halting of the shorter program:

x=4;for(y=3;x/y%y;y*=2) x*=5;


(containing 28 characters) is also unknown. It is based on my conjecture that $\left\lfloor \frac {4 \times 5^n}{3 \times 2^n} \right\rfloor \bmod{(3 \times 2^n)} \ne 0$ for all $n \ge 0$. I have verified this up to n = 100,000. The conjecture is similar to a simpler one concerning $\left\lfloor \frac {7^n}{2^n} \right\rfloor \bmod{2^n}$. See math.stackexchange.com/questions/214319

EDIT (Oct 27):

I conjecture that the halting of the even shorter program:

for(x=y=2;x/y%y;y*=2)x*=5;


(containing 26 characters) is also unknown. It is based on another conjecture that $\left\lfloor \frac {5^n}{2^n} \right\rfloor \bmod{(2^{n+1})} \ne 0$ for all $n \ge 0$.

-
The Collatz conjecture might be a candidate. – marty cohen Dec 7 '12 at 6:53