24 September 2015

The 3n+1 conjecture


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.

14 comments:

  1. NepkarelSeptember 25, 2015 at 11:16 AM

    Isn't it just a matter of waiting until you hit a number that is an even multiple of 2^n?

    ReplyDelete
    Replies
    1. MinnesotastanSeptember 25, 2015 at 12:16 PM

      That 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.

      Delete
  2. AnonymousSeptember 25, 2015 at 1:05 PM

    The 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.

    I 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)


    ReplyDelete
  3. not securely anchoredSeptember 25, 2015 at 1:23 PM

    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

    ReplyDelete
    Replies
    1. MinnesotastanSeptember 25, 2015 at 2:49 PM

      I'm not on Facebook, but I was able to view the image. Very nice - I like it when manual labor shows true craftsmanship.

      Delete
  4. AnonymousSeptember 25, 2015 at 1:26 PM

    why 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?

    I-)

    ReplyDelete
    Replies
    1. AnonymousSeptember 25, 2015 at 3:04 PM

      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.

      But with the 3n+1 rule, it's not so simple. It's a famous unsolved problem in mathematics.

      Delete
  5. AnonymousSeptember 27, 2015 at 12:20 AM

    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:

    1 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

    ReplyDelete
    Replies
    1. MinnesotastanSeptember 27, 2015 at 8:14 AM

      Interesting. And of course there will be (n)n + 1 conjectures for you to keep. Should keep you busy this winter.

      Delete
    2. AnonymousSeptember 27, 2015 at 1:54 PM

      could anyone share the excel code that will do this 3n+1 problem?

      I-)

      Delete
    3. AnonymousSeptember 28, 2015 at 6:04 PM

      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).

      Delete
    4. AlexSeptember 28, 2015 at 6:08 PM

      This comment has been removed by the author.

      Delete
    5. AnonymousSeptember 28, 2015 at 6:08 PM

      For those who have access to matlab, heres the code I used: http://pastebin.com/UunR6Mj4

      Delete
    6. AnonymousSeptember 29, 2015 at 10:13 AM

      thanks for the matlab link!

      I-)

      Delete