Register to reply

Hailstone Sequence

by Pupil
Tags: hailstone, sequence
Share this thread:
Pupil
#1
Jul6-09, 10:00 PM
P: 136
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?
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
CRGreathouse
#2
Jul6-09, 11:09 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by Pupil View Post
Think it will ever be proved?
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
#3
Jul6-09, 11:19 PM
P: 136
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
#4
Jul7-09, 08:13 AM
P: 607
Hailstone Sequence

Quote Quote by Pupil View Post
Suppose you pick a random integer n.
Correction: positive integer. There are cycles other than the "1" cycle if you allow negative integers.
DaveC426913
#5
Jul7-09, 08:34 AM
DaveC426913's Avatar
P: 15,319
I played with this once on a plane trip with pencil and paper. Yeah, 27 was a doozy.
Dragonfall
#6
Jul7-09, 10:09 AM
Dragonfall's Avatar
P: 993
I got 10$ on this being undecidable by ZFC axioms.
Pupil
#7
Jul7-09, 02:55 PM
P: 136
Quote Quote by DaveC426913 View Post
I played with this once on a plane trip with pencil and paper. Yeah, 27 was a doozy.
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
#8
Jul9-09, 11:26 AM
P: 105

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
#9
Jul9-09, 12:23 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by Dragonfall View Post
I got 10$ on this being undecidable by ZFC axioms.
I'll take you up on that.


Register to reply

Related Discussions
Calculating the pressure of a hailstone Advanced Physics Homework 1
Formula for the sequence c defined by Sequence b Calculus & Beyond Homework 17
What is the next term in this sequence? E1 O2 E3 R4 E5 X6 Fun, Photos & Games 3
Proving a given sequence is a delta sequence ~ Calculus & Beyond Homework 1
Record Hailstone Reported in Neb. Storm: Newsday.com Biology 0