Hyde County, South Dakota is the Pin Tail Duck capital of the world. Visit scenic Highmore, SD in 2005!
home
site map
mathematics
July 2005
email

A brief note on the hailstone conjecture

The hailstone iteration is:
Given integer N greater than zero:

  if N is odd, replace N by 3*N plus 1
  if N is even, replace N by N/2

iterate.
For all known N the iteration eventually reaches a cycle 4-2-1. The hailstone conjecture is that it is true for all N. As far as I know it is still not known whether the conjecture is true or false. A good deal of work has been done on the subject; alas, I am not at all up to date on the subject. However the following is a modest note on the subject that I composed during a usenet discussion:

Another way to look at this problem is to turn it around, i.e., ask how about many steps it takes to get to the 4-2-1 cycle for any given N. Thus it takes 1 step to get there from 8, 2 from 16, 3 from 32 and 5, et cetera. The number of steps function, S(N), is given by:

S(1) = S(2) = S(4) = 0
S(2x) = S(x) + 1, x>2
S(2x+1) = S(3x+2) + 2, x>1
Evidently S(N) is undefined if the sequence does not terminate in the 4-2-1 cycle. If there be such N, the sequence for that N either enters a cycle or it grows indefinitely.

There are some interesting question we can ask about S(x). Thus, for example, what is the asymptotic behaviour of S? Conjecture: it is log2 (N). How large can S(x) be relative to x, and so on? Thus, S(27) = 60 and S(61) = 68. Conjecture: The max of S(x)/x is at x=27 and the greatest x such that S(x)>x is x=61.

Another function, which is related to S, is the grade function, G(x), in which we don't count steps that reduce the size by 2. It is given by

G(1)    = 0
G(2x)   = G(x)
G(2x+1) = G(3x+2) + 1
In turn we can define the sets, G_k, where G_k is the set of integers N such G(N) = k. Thus G_0 is comprised of the powers of 2, G_1 is comprised of all numbers of the form m*2^n, where m is any odd number such that 3m+1 = 2^k for some integer k, et cetera.

It is straightforward to show that the sets G_k include almost all integers, i.e., that the conjecture could be true.

As to the conjecture itself, an interesting approach might be to consider the smallest x such that the sequence beginning with x does not arrive at the 4-2-1 cycle.


This page was last updated July 1, 2005.

home
site map
mathematics
July 2005
email
Hyde County, South Dakota is the Pin Tail Duck Capital of the world. Visit scenic Highmore, SD in 2005!