On Sunday morning the 25th of June 1998 I was woken at 6am by the scratching sounds of a cat trying to bury a pool of it's stinking number ones on a rug in the Computer Room. After half an hour of cleaning I knew there was no point in trying to go back to sleep, so I doodled on my PC for a while trying to think of something to do.
For some unknown reason I began to think about the old Hailstone Numbers from my school days. Calculating these number sequences became a bit of a fad (like Conway's game of Life) back in the early computer days. I think it was the early 1970s, long before personal computers were conceived. I remember reading somewhere at the time that calculating the sequences wasted so much computer time that they were regarded as a communist plot to undermine computer research in the western world.
As a reminder, Hailstone Numbers go like this:
Starting with any positive integer n, form a sequence in the following way:
Generate the sequence from the starting number and you'll find the numbers go up and down like a hailstone in a cloud before it plummets to earth. It is speculated that all sequences eventually fall back to 1 and go into an endless loop 1,4,2,1,4,2..., but a quick web search hints that this remains an outstanding mathematical problem. References:
J.C. Lagarias, The 3x+1 problem and its
generalizations
|
NOTE: The sequences can be simplified by making the odd iteration step n=(n*3+1)/2. This combines an odd iteration with the even one which must follow it. The resulting sequences are a bit easier to handle in this form, but for my simple experiments I decided to stick with the traditional wording of the problem.
To give you an idea of how haphazard the sequences are, here is a plot of the sequences for the starting numbers 11, 30 and 51.
It's interesting to look at the lengths of the sequences, which also seem to be rather haphazard. This is a plot of the sequence length for the starting numbers 1 to 200.
There is a tantalizing pattern embedded in the plot, where the lower limit of the lengths seems to slowly increase in a vaguely logarithmic way. I wondered how the law of large numbers applied to the lengths of Hailstone sequences. Using Mathematica 2.2 I wrote a program to plot the average sequence lengths for very large numbers, hoping to see some kind of long term pattern in the lengths of the Hailstone sequences.
Some simple experiments showed that Mathematica could generate the Hailstone sequence for a 300 digit starting number in about a second. This led me to compose the following program which samples the lengths of sequences on ranges of powers of 10.
(* --- One iteration of the sequence --- *)
hailiter[n_Integer] := If[EvenQ[n],n/2,3n+1]
(* --- Return the maximum value reached and the length of a Hailstone Sequence
for a given starting number 'n' --- *)
hailseq[n_Integer] := Module[{num=n,max=0,count=0},
While[num>1,
count++;
num = hailiter[num];
If[num>max,max=num];
];
Return[{n,max,count}];
];
(* --- In a loop from 1 to 'n', take the average sequence lengths of
'samps' random starting points between the successive 10^n, generate
a list plot of the resulting table --- *)
hailpowers[n_Integer,step_Integer,samps_Integer] := Module[{lst={},av,t,tt},
Do[
t = Table[hailseq[Random[Integer,{10^x,10^(x+1)-1}]],{samps}];
tt = Flatten[Map[Take[#,-1]&,t]];
av = Apply[Plus,tt] / Length[tt];
lst = Append[lst,{x,av}];
Print[{x,N[av]}],
{x,1,n,step}];
ListPlot[lst,PlotJoined->True,
PlotStyle->{AbsoluteThickness[.1]},
AxesOrigin->{0,0},GridLines->Automatic,
Frame->True,FrameLabel->{"10^n","Sequence Length"},
PlotLabel->FontForm["Hailstone Sequences",{"Arial",16}]];
Return[lst];
];
hailrun[300,1,3]
This generates a plot of the average sequence lengths of 3 randomly chosen starting points in ranges of powers of ten from 1 to 300 in steps of 1. The calculation took about 80 minutes on a 200MHz Pentium II Pro.
This plot supplies numerical evidence that the average length of Hailstone sequences increases in a very slow and almost perfectly logarithmic manner (remembering that this plot has an exponentially increasing horizontal axis).
To examine the possible logarithmic relationship more closely we can run another test that reaches even higher powers of ten, taking more random samples, but increasing the step size to save time. Now we sample 10 random starting points in ranges of powers of 10 from 1 to 501 in steps of 100, a total of 60 samples. Total calculation time is about 5 minutes.
seq = hailpowers[501,100,10];
The resulting plot of the average lengths is nearly a straight line. Now we get a fit function for the sequence, not forgetting to expand the horizontal axis values out exponentially so we're fitting the actual values.
pow10[n_Integer] := Power[10,n];
pow10seq = Map[{pow10[#[[1]]],#[[2]]}&,seq]; (* expand axis 10^n *)
ffunc = Fit[pow10seq,{Log[z]},z]
10.3104 Log[z]
This is a very good fit for the previous sequence. Plotting the fit function and the sequence together produces an almost perfectly overlapping pair of lines (not shown). This supplies a bit more evidence that the lengths of Hailstone Sequences increases in a very slow logarithmic manner.
I'm quite curious about this number 10.3104 that pops out of the Fit, and I'd love to hear from someone who can explain if it can be explicitly calculated.
Many runs of generating the plots over a period of a few hours has tested sequences with several thousand random starting numbers up to 10^500. So far, all of the sequences have fallen to earth and hit 1, even after almost 12000 iterations. This supplies weak evidence that Hailstone Numbers always fall to the ground, eventually.
In March 2005 I received an email from Rob van den Tillaart who said that he and his colleague Jack van der Elsen had published a paper titled An Investigation in the Hailstone Function which was apparently inspired by this web page. Rob said I may attach a copy of the paper to this site, but asked that I reference the papers of Legarias .
Rob and Jacks' paper
See also: