Wednesday, September 14, 2005

Collatz on a random Huge Integer

I've been running the 3N+1 sequence on a randomly chosen 200,000-bit integer, in hopes that non-4-2-1-terminating numbers become far more frequent at higher values. It's now been running 5.8 days and still hasn't terminated. My implementation is very slow, so I don't know what this means, yet. I unfortunately don't print out iteration numbers as I go, nor do I checkpoint. It is supposed to stop if it iterates 100 times longer than the number of bits it started out with.

It hasn't run out of memory, so the values aren't growing vastly unbounded in size.

1 comment :

the end is nigh said...

It doesn't matter how big a number you chose the iteration allways converges to the 21 cycle.
The 3n+1 conjecture cannot be proven computationally, but it can be proved to be false if there exists a number that doesn't converge to 1.
Suppose that the conjecture is false, then there exists a number s, which is the smallest number that doesn't converge to 1, under iteration of the function
T(x):=If[x is odd 3x+1, ELSE x/2]
thus T(s) must be bigger otherwise T(s) replaces s as being the smallest number that doesn't converge to 1, which a contadiction. Repeating this argument it's clear that all of the numbers that you obtain from the foward iteration of s must all be
1) bigger than s if then are odd
2) bigger that 2s if they are even
So let us call all of these numbers the set S+. Then S+ is a subset all of the odd numbers that are bigger than s and all of the even numbers that are bigger than 2s....