Take any whole positive number.
If it is an even number, divide it by 2.
If it is an odd number, multiply it by 3 and add 1.
Repeat whichever above step applies, over and over again.
The end result will always be the number 1.
For example: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
The graph at the top shows the resulting sequence generated when starting with the number 27, with these intermediate steps:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Nobody understand why this happens. The conjecture has been checked by computer for all starting values up to 264. More at the Wikipedia entry.
Isn't it just a matter of waiting until you hit a number that is an even multiple of 2^n?
ReplyDeleteThat of course is how all the sequences end. What hasn't been discovered, to my understanding, is proof that every possible number you could start with will eventually generate that terminal sequence.
DeleteThe core of this argument is whether or not 3*N+1 produces a limited set of values, which does not include 2^N. Any whole number multiplied by 3 and increased by 1 is an even number. If at any point, the series generation produces a even number value that is 2^N, then it devolves to 1.
ReplyDeleteI suspect, without being able to prove it, that 3*N+1 is an open set, where the values are unranged -- that is you can generate a very wide set of values using this. There is no restriction to avoid values of 2^N, so eventually after a number of tries, you will get to 2^N, and the series collapses to 1.
Now proving this is going to be difficult. You might want to try proving it to look at under what conditions 3*N+1 = 2^M (where N and M are integers)
Off topic and don't know if you will be able to view it; sweet example of WPA stonework in Kansas cemetery: https://www.facebook.com/indysights/photos/a.1494811677474754.1073741842.1494417484180840/1634775910144996/?type=3&theater
ReplyDeleteI'm not on Facebook, but I was able to view the image. Very nice - I like it when manual labor shows true craftsmanship.
Deletewhy bother with the '3n+1' for converting the odd number to an even number? why not just add 1 to the odd number, get the even number, and continue dividing by 2 until you get to 1?
ReplyDeleteI-)
It's not too hard to show that this modified rule will indeed always reach 1. That's because the number will always go down at each step, until it reaches 1. The reason is that if n is odd and n>1, then (n+1)/2 is always smaller than n. And if n is even and n>1, then certainly n/2 is smaller than n. So the number keeps going down until n=1.
DeleteBut with the 3n+1 rule, it's not so simple. It's a famous unsolved problem in mathematics.
I played around a bit with a 5n + 1 conjecture, to see how that would work. Here's the result for the first 5 numbers:
ReplyDelete1 6 3 16 8 4 2 1
2 1
3 16 8 4 2 1
4 2 1
-BUT-
5 26 13 66 33 166 83 416 208 104 52 26 13 ...
results in a never-ending loop. Not a sequence that increases forever, or settles to 1, but a sequence that drops to 13 every 10 numbers. Weird.
Lurker111
Interesting. And of course there will be (n)n + 1 conjectures for you to keep. Should keep you busy this winter.
Deletecould anyone share the excel code that will do this 3n+1 problem?
DeleteI-)
I don't have excel code, but I became curious last night and wrote up a matlab script to attempt to find any loops (within the first 1000 steps) for any set of numbers you like. All numbers between 1 and 10000 settle on a loop within the first 100 steps for 3n+1. For 5n+1, the numbers that converge within 1000 steps are few and far between - when they do converge, it's almost always within the first 200 steps (for n<10000).
DeleteThis comment has been removed by the author.
DeleteFor those who have access to matlab, heres the code I used: http://pastebin.com/UunR6Mj4
Deletethanks for the matlab link!
DeleteI-)