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. 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
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.
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 =)
 Display posts from previous: All Posts Oldest FirstNewest First
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.

»
 Page 1 of 1 » All times are GMT - 5 Hours