Conference rusure::math

998.0. "auxiliary problem about hailstorm function" by HANNAH::OSMAN (type hannah::hogan$:[osman]eric.vt240) Tue Dec 27 1988 10:30

    Please see note 249 for background of the following math problem:
    
    	Consider a hailstorm cycle which takes an odd positive integer
    	to another odd positive integer like this:
    
    		NEW = (OLD*3+1)/2/2/2/2/2/2/2/2...
    
    	That is, you divide by 2 as much as necessary to make NEW be odd.
    
    	Prove that for all positive integers N, there exists a set
    
    		S(N)
    
    	of numbers that require at least N cycles to reach the integer 1.
    
    	For example, try 7.  One cycle is (3*7+1)/2, or 11, and two cycles
    	is (3*11+1)/2 or 17, and three cycles is (3*17+1)/4 or 13, and four
    	cycles is (3*13+1)/8 or 5, and five cycles is (3*5+1)/16 or 1.
    
    	So 7 takes 5 cycles.  Hence
    
    		s(5)={7,...}
    
    	So for N=5, we've proved the conjecture.
    
    	Another way of stating the conjecture, is that although the
    	grand conjecture of claiming that all numbers lead to 1 is not
    	proved, perhaps we can prove this simpler conjecture that shows
    	that numbers can be found that lead to 1 but take arbitrarily as
    	long as we like to get there.
    
    /Eric

    Let S(N) be the set of odd numbers that require exactly N cycles (as
    described in .0) to reach the integer 1.
    
    Choose an element p of S(N).  Suppose p = 3*s+2.  Now 2*s+1, 8*s+5,
    32*s+21, ..., (2*4^k)*s + (4*4^k-1)/3, ... are all members of S(N+1),
    because one cycle leads them to p.  Suppose p = 3*s+1; now 4*s+1,
    16*s+5, ..., (4*4^k)*s + (4*4^k-1)/3, ... are all members of S(N+1).
    
    If p = 3*s, there is no value that leads to p in one cycle.  However,
    the above construction shows that for every N, S(N) contains an infinite
    number of values that aren't multiples of 3.  Thus, for any non-empty S(N),
    the above construction produces an infinite number of elements in S(N+1).
    
    By induction, every S(N) contains an infinite number of elements.

There's a lot of recent ideas about this problem - and a 'Mathematica' program 
to investigate it - in the recently published 'Computational Recreations in 
Mathematica' (Author: Vardi) by Addison-Wesley. Anyone for rewriting it in 
MAPLE?