Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
Lew knows about this, but others may benefit by perusing… –  Gerry Myerson Oct 11 '12 at 3:42

1 Answer 1

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

EDIT (Oct 27):

I conjecture that the halting of the even shorter program:


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

share|cite|improve this answer
The Collatz conjecture might be a candidate. –  marty cohen Dec 7 '12 at 6:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.