A brief note on the hailstone conjectureGiven 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>1Evidently 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) + 1In 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. |