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