Collatz Conjecture
Let x(n+1)=xn/2 [xn even] or =3*xn + 1 [xn odd]
Let x0 be any positive integer, then the series will terminate at xm=1, for some m
Proof:
(a) xn==0 [mod 2] => x(n+1)=xn/2 <xn
(b) xn==1 [mod 4] ==-1 [mod 2] => x(n+3)=(3xn + 1)/4 <xn [xn>1]
(c) xn==-1 [mod 2**(i+1)] => x(n+2)=(3xn + 1)/2==-1 [mod 2**i] >xn [xn>-1]
As soon as (a) or (b) occurs, sequences go to a smaller number, so responsibility for termination is transferred to that number. Therefore, by induction, an infinite chain could not have any (a) or (b), but would need an infinite initial string of (c).
=> x0==-1 [mod 2**99999…] = -1
Copyright 1998 James Wanless