3
$\begingroup$

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.

  • 0
    Lew knows about this, but others may benefit by perusing http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown2012-10-11

1 Answers 1

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

  • 0
    The Collatz conjecture might be a candidate.2012-12-07