Flofloflo
Member
Joined: 07 Nov 2007 Posts: 120

Posted: 01 Jul 2009 06:15:13 pm Post subject: 


Hello,
There's a thing I wrote about the collatz conjecture some time ago, predicting the amount of steps one can expect untill a number reaches 1.
(in case people don't know the collatz conjecture:Take a random number, if it's odd, multiply by 3 and add 1. If it's even, divide by 2. If you repeat these steps each number seems to go to 1)
So I was wondering if somebody could tell me how much sense it makes what I write? =) (btw sorry but I am not capital sensitive when it comes to variables)
Collatz:
Taking a random, even integer, A.
The chance A can be devided by 2^1 is 1/2^0 . The chance a can be divided by 2^2 = 1/2^1. P(2^3) = 1/2^2 Etc.
This means, if you want to divide a random number by a number T=2^x, with a value for x as big as possible you get:
x = 1/2^0 + 1/2^1 +1/2^2....1/2^n
2x = 1/2^1+ 1/2^0 .... 1/2^(n1)
x = 1/2^1  1/2^n = 2.
Conlusion, the expected value for 2^x = 4.
Now, for the collatz conjecture, you multiply an odd number by 3, you add one, and then divide by 2^x, where x is as big as possible, and I just showed the expected value of x is 2.
This means the average growth after each 3 steps is (3x+1)/4 = 0,75x+0,25.
Every number higher then 2, except for 4 and 8, will eventually reach 16, and go to 1 from there on.
Let's say you start with an odd number Y.
Every step, you multiply by 0,75 and add 0,25:
1) 0,75Y+0,25
2) 0,75(0,75Y+0,25)+0,25
N) 0,75^n * Y+ 0,25* ∑0,75^i (i from 1 to N1)
S = 0,75^1+0,75^2 .... 0,75^(n1)
0,75S= 0,75^2 + 0,75^3 .... 0,75^n
0,25S = 0,75  0,75^n
S = 3  4 * 0,75^n
N) 0,75^N * Y + 0,75  0,75^N = 0,75^N * ( Y1) + 0,75
Now, after N steps, this will reach 16.
0,75^N (Y1) + 0,75 = 16
0,75^N = 15,25 / (Y1)
N = LOG(15,25/(Y1))/Log(0,75)
Now, we still have to multiply N by 3 (because N is the amount of sets of 3 steps) and we have to add 4 because N
is only the amount of steps to reach 16.
Conclusion:
An approximation for the amount of steps needed to reach 1 with the collatz alogrithm, starting at Y is:
4+(3LOG(15,25/(Y1))/Log(0,75)
Last edited by Guest on 01 Jul 2009 06:18:28 pm; edited 1 time in total 

DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 01 Jul 2009 08:03:18 pm Post subject: 


Makes sense, although you're going to confuse all the Americans here writing commas in your decimals.
Unfortunately, knowing that it's overwhelmingly likely that a number eventually reaches 1 tells us nothing as far as the conjecture is concerned. If there's only a few counterexamples (relatively speaking, I mean  they'd still be infinite, because you could multiply them by any power of 2) then the probability that a number converges to 1 might still be very high  in fact, the probability might be 1. It's a good argument for why the conjecture ought to be true, but it doesn't get us a proof. 
