Hailstone Sequence

Pupil

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:

http://www.mediafire.com/?sharekey=f...4e75f6e8ebb871

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?

CRGreathouse

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

Pupil

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.

g_edgar

Correction: positive integer. There are cycles other than the "1" cycle if you allow negative integers.

DaveC426913

I played with this once on a plane trip with pencil and paper. Yeah, 27 was a doozy.

Dragonfall

I got 10$ on this being undecidable by ZFC axioms.

Pupil

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.

Mensanator

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.

CRGreathouse

I'll take you up on that.