[comp.theory] Unknown proofs

markh@csd4.csd.uwm.edu (Mark William Hopkins) (04/29/91)

In article <4026@bruce.cs.monash.OZ.AU> mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) writes:
>Yes.  Pick any famous unsolved mathematical theorem, and try to solve
>it by brute force - i.e. prove that this one terminates:
>
>read x
>while (x > 1)
>    if x mod 2 = 0 then
>	x = x / 2
>    else
>	x = 3 * x + 1

Actually, there is a relatively simple proof that uses the irrationality of
log(3)/log(2), but unfortunately I haven't the time to go into it: our system's
gonna go down and I have to finish some major projects. :) :)

Play around with the function

		       f(1) = 0
		       f(2n) = f(n) + 1
		       f(2n + 1) = f(3n + 2) + 2

for a while.  Maybe you'll see it...