Mathematical mysteries: Hailstone sequences

Issue 1
January 1997


This problem is easy to describe but it is one of mathematics' unsolved problems.

Starting with any positive integer n, form a sequence in the following way:

  • If n is even, divide it by 2 to give n' = n/2.
  • If n is odd, multiply it by 3 and add 1 to give n' = 3n + 1.

Then take n' as the new starting number and repeat the process. For example:

n = 5 gives the sequence
5, 16, 8, 4, 2, 1, 4, 2, 1,...
n = 11 gives the sequence
11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

These are sometimes called "Hailstone sequences" because they go up and down just like a hailstone in a cloud before crashing to Earth - the endless cycle 4, 2, 1, 4, 2, 1. It seems from experiment that such a sequence will always eventually end in this repeating cycle 4, 2, 1, 4, 2, 1,... and so on, but some values for N generate many values before the repeating cycle begins. For example, try starting with n = 27. See if you can find starting values that generate even longer sequences.

An unsolved problem is, can it be proved that every starting value will generate a sequence that eventually settles to 4, 2, 1, 4, 2, 1,...? Could there be a sequence that never settles down to a repeating cycle at all?

Hailstone Evaluator

Enter any positive integer, the Hailstone sequence will be returned.

Comments

If there is a counterexample to Collatz

If there is a counterexample to the Collatz conjecture there is a minimum counterexample and it must be equivalent to 3 mod4.

Goes into an infinite loop

Goes into an infinite loop and hangs when asked to evaluate 0.

Simple version?

Hi.
If you change the steps to an much easier version:
if even divide by 2.
if odd add one.
Then you clearly always will end opp with 1. I`m not sure though how to write a proof of this, but you will always end up with the sequence (for n bigger than 2) 4,2,1,
Somehow related?

this is easy to prove

Consider that the n+2 iteration of the function is always less than the nth iteration.

Result for any number

Whatever number you enter, before the first 4 appears, the previous 6 numbers are always same (40,20,10,5,16,8). If it is an even number, it is preceded by 26,13 and if it is odd, then 80 and 160.

Exception

Not necessarily. Any power of 2 will just be devided by two over and over again and reach 16 without going through 5 first.

Answer

The number is divided by 2. If the resulting number is not a whole number, it is multiplied by 3 and 1 is added. Otherwise it is divided by 2 again.

the mother function of 3n+1

there i s function that when you let n=1 the collatz problem appears. but also, when N=-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8...,infinity. as you guys can see, if we solve 3n +1, we will solve all of them. with the function is easy to find and loo of every roblem. why all numbers top at 1, is just because there are not positive numbers less than 0.

Something to think about...

It would be very interesting to know whether or not "stopping length" as a function of n exhibited any regularity, and if so, of what nature? If you plotted the "stopping length" of each sequence against the unique n that generated it, what would the graph look like?

Maybe someone with some programming ability can try this out...

Good idea!

Challenge accepted.

There is an obvious pattern

Try 55, 115, 175, 235. All these have something in common

List of Lengths

My lengths are defined by stopping once a 4 is reached.

n=5 len=3
n=6 len=6
n=7 len=14
n=9 len=17
n=18 len=18
n=25 len=21
n=27 len=109
n=54 len=110
n=73 len=113
n=97 len=116
n=129 len=119
n=171 len=122
n=231 len=125
n=313 len=128
n=327 len=141
n=649 len=142
n=703 len=168
n=871 len=176
n=1161 len=179
n=2223 len=180
n=2463 len=206
n=2919 len=214
n=3711 len=235
n=6171 len=259
n=10971 len=265
n=13255 len=273
n=17647 len=276
n=23529 len=279
n=26623 len=305
n=34239 len=308
n=35655 len=321
n=52527 len=337
n=77031 len=348
n=106239 len=351
n=142587 len=372
n=156159 len=380
n=216367 len=383
n=230631 len=440
n=410011 len=446
n=511935 len=467
n=626331 len=506
n=837799 len=522
n=1117065 len=525
n=1501353 len=528
n=1723519 len=554
n=2298025 len=557
n=3064033 len=560
n=3542887 len=581
n=3732423 len=594
n=5649499 len=610
n=6649279 len=662
n=8400511 len=683
n=11200681 len=686
n=14934241 len=689
n=15733191 len=702
n=31466382 len=703
n=36791535 len=742
n=63728127 len=947
n=127456254 len=948
n=169941673 len=951
n=226588897 len=954
n=268549803 len=962
n=537099606 len=963
n=670617279 len=984

working on it....

Can you find out if the frequence of odd and even "len"s is 50% or not?

code error

i tested you program and it failed for number 5
the sequence for 5 is 5, 16, 8, 4, 2, 1 definitly not 5, 16, 8, 4, 2, 1, 4, 2, 1,...

Um not wrong

5 DEFINETLY DOES go 5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1.... The issue is that there are only 6, 4 or 3 numbers there that matter (depending on how you count)
You are either counting the 5,16,8 (so 3), the 5,16,8,4 (so 4, counting until you reach a 4) or 5,16,8,4,2,1 (so 6, counting until the repetition would start)

The sequence NEVER ENDS, but all (needs proof) eventually repeat 4,2,1,4,2,1 and so each sequence, even for the number 4 is infinitely long, we just don't care about after the repetition.

Perhaps you should re-read the article, and consider the original commentators work. The reason you are disagreeing seems as simple as how are you counting. You each are counting in a different way, yet seem to be saying the exact same thing.

The question isn't whether definitionally if 0 is or is not a natural number, you have to define whether it is and then do the math accordingly. I always asked my professors if they considered 0 in N or not for their classes. The guy you are saying is wrong, just defined his algorithm differently than you did. It isn't that you are right and he is wrong, or vice versa, it is that you both defined what you are looking for differently, but still validly.

Same holds for Fibonacci, does Fib start at 0 or at 1? If 0 is in N than the explicit formula for fibonacci is also different, yet they all are the same if you change the initial definitions to match.

code error

when you get to 1 (which is odd) the next result is 4, 2, 1....

I think you missed the point

Try reading the article next time...
It seems from experiment that such a sequence will always eventually end in this repeating cycle 4, 2, 1, 4, 2, 1,...

Collatz

This is also called the Collatz conjecture. This is the name of the unsolved problem. Perhaps you should mention this in the article

Hailstone

It's also called: The Ulam sequence