Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Math and Science => Technology & Calculator Open Topic
Author Message
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^(n-1)
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 N-1)
S = 0,75^1+0,75^2 .... 0,75^(n-1)
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 * ( Y-1) + 0,75
Now, after N steps, this will reach 16.
0,75^N (Y-1) + 0,75 = 16
0,75^N = 15,25 / (Y-1)
N = LOG(15,25/(Y-1))/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/(Y-1))/Log(0,75)


Last edited by Guest on 01 Jul 2009 06:18:28 pm; edited 1 time in total
Back to top
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.
Back to top
Flofloflo


Member


Joined: 07 Nov 2007
Posts: 120

Posted: 02 Jul 2009 06:52:35 am    Post subject:

Yes, I know, this isn't any proof or something... It's just a way to approximate the amount of steps required. I still gotta check if my average amount of steps for, say, the first 200 series is approximatly the same as the actual average amount of steps =)
Back to top
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement