Hailstone Sequence

  1. Suppose you pick a random integer n. If it is even, divide the number by 2, if it is odd, multiply it by three and add 1 and repeat. People think that no matter what integer you pick, it will always end up oscillating between 4, 2, 1, 4, 2, 1, 4, 2, 1...But no one has proved it yet. I looked it up and came across this: http://en.wikipedia.org/wiki/Hailstone_sequence

    For fun I wrote a program to evaluate the hailstone sequence for any n you choose and uploaded it here:


    You might check it out. I've tried probably a hundred different values of n and they all end up 4, 2, 1...

    Think it will ever be proved?
  2. jcsd
  3. CRGreathouse

    CRGreathouse 3,497
    Science Advisor
    Homework Helper

    Probably not in my lifetime. It's a very hard problem. Maddeningly easy to check individual cases, but hard to prove the whole thing.

    It's been checked up to very high bounds (sorry, don't know how high off the top of my head).
  4. Maybe it'll turn out to be the next Fermat's Last Theorem? Knowing it hasn't been solved makes me want to play around with it myself, but I'm barely a freshman Calculus I student myself, there's no way I'd figure anything out. :shy:
  5. Correction: positive integer. There are cycles other than the "1" cycle if you allow negative integers.
  6. DaveC426913

    DaveC426913 16,346
    Gold Member

    I played with this once on a plane trip with pencil and paper. Yeah, 27 was a doozy.
  7. I got 10$ on this being undecidable by ZFC axioms.
  8. Bah! Never do odd integers, they take way longer to come down to 4, 2, 1 than the even integers, or at least that's been my experience playing around with the program I wrote.

  9. Fun stuff. For example, take the sequence from 27 and stop at 31: 27-82-41-124-62-31 and count the evens and odds.

    1 odd
    1 even
    1 odd
    2 evens

    Now, the successor of an odd is always even, so there can never be more than one contiguous odd. But there can arbitrarily many contiguous evens. So we can describe the sequence by listing the size of the even blocks (with the assumption every block of evens is seperated by a single odd). For the above, the list is [1,2]. The sequence from 11 to 1 would be [1,2,3,4] read as

    1 odd
    1 even
    1 odd
    2 evens
    1 odd
    3 evens
    1 odd
    4 evens

    (I'll leave it up to the reader to verify.)

    It can be proved that ANY possible list of integers (where all are >0) appears infinitely many times. For example, that example from 27 to 31 is just one instance of the [1,2] pathway. Others are:

    3 to 4
    11 to 13
    19 to 22
    27 to 31
    35 to 40
    43 to 49
    51 to 58
    59 to 67
    67 to 76
    75 to 85

    Note that 67 appears as both a starting point and an ending point. This means the [1,2] sequence is followed by another [1,2] sequence, or more precisely, 59 to 76 is a [1,2,1,2] sequence. That's referred to as a 2nd generation Type [1,2] sequence. [1,2,1,2,1,2] is a 3rd generation, [1,2,1,2,1,2,1,2] is a 4th generation, etc. Of course, there are infinite generations, each of which contain infinite elements.

    Furthermore, note that 31 happens to be a Mersenne Number. Had we kept going we would have hit another at 2047. And of course, there are an infinite number of them. For an infinite number of generations.

    And there's a nice little closed form expression to find the ith, kth generation:

    Type[1,2]MH(k,i) = 2**(6*((i-1)*9**(k-1)+(9**(k-1)-1)//2+1)-1)-1

    You probably don't want to try this by hand as the numbers get REALLY big, really fast. Type[1,2]MH(6,1), the first element of generation 6, i.e., [1,2,1,2,1,2,1,2,1,2,1,2]
    that's a Mersenne number, has 53338 decimal digits. I won't list it here. Takes about 6 sheets of 11x17 paper at the smallest font to print it.

    None of this, however, suffice as proof because it would need to be shown that all these infinite pathways are connected.
    Last edited: Jul 9, 2009
  10. CRGreathouse

    CRGreathouse 3,497
    Science Advisor
    Homework Helper

    I'll take you up on that.
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?