The Hailstone sequence of numbers can be generated from a starting positive integer,   n   by:

   If   n   is     1     then the sequence ends.
   If   n   is   even then the next   n   of the sequence    = n/2 
   If   n   is   odd   then the next   n   of the sequence    = (3 * n) + 1 


The (unproven) Collatz conjecture is that the hailstone sequence for any starting number always terminates.



This sequence was named by Lothar Collatz in 1937   (or possibly in 1939),   and is also known as (the):

   hailstone sequence,   hailstone numbers
   3x + 2 mapping,   3n + 1 problem
   Collatz sequence
   Hasse's algorithm
   Kakutani's problem
   Syracuse algorithm,   Syracuse problem
   Thwaites conjecture 
   Ulam's problem


The hailstone sequence is also known as   hailstone numbers   (because the values are usually subject to multiple descents and ascents like hailstones in a cloud).



Task

 Create a routine to generate the hailstone sequence for a number.
 Use the routine to show that the hailstone sequence for the number 27 has 112 elements starting with 27, 82, 41, 124 and ending with 8, 4, 2, 1
 Show the number less than 100,000 which has the longest hailstone sequence together with that sequence's length.
   (But don't show the actual sequence!)


See also

   xkcd (humourous).
   The Notorious Collatz conjecture Terence Tao, UCLA (Presentation, pdf).
   The Simplest Math Problem No One Can Solve Veritasium (video, sponsored).


MODULE hailst;
 
IMPORT  Out;
 
CONST   maxCard         = MAX (INTEGER) DIV 3;
        List            = 1;
        Count           = 2;
        Max             = 3;
 
VAR     a               : INTEGER;
 
PROCEDURE HailStone (start, type  : INTEGER) : INTEGER;
 
VAR     n, max, count           : INTEGER;
 
BEGIN
  count := 1;
  n := start;
  max := n;
  LOOP
    IF  type = List  THEN
      Out.Int (n, 12);
      IF  count MOD 6 = 0  THEN  Out.Ln  END
    END;
    IF  n = 1  THEN  EXIT  END;
    IF  ODD (n)  THEN
      IF  n < maxCard  THEN
        n := 3 * n + 1;
        IF   n > max  THEN  max := n  END
      ELSE
        Out.String ("Exceeding max value for type INTEGER at: ");
        Out.String (" n = ");           Out.Int (start, 12);
        Out.String (" , count = ");     Out.Int (count, 12);
        Out.String (" and intermediate value ");
        Out.Int (n, 1);
        Out.String (". Aborting.");
        Out.Ln;
        HALT (2)
      END
    ELSE
      n := n DIV 2
    END;
    INC (count)
  END;
  IF  type = Max  THEN  RETURN  max  ELSE  RETURN  count  END
END HailStone;
 
 
PROCEDURE FindMax (num   : INTEGER);
 
VAR     val, maxCount, maxVal, cnt      : INTEGER;
 
BEGIN
  maxCount := 0;
  maxVal := 0;
  FOR  val := 2 TO num  DO
   cnt := HailStone (val, Count);
    IF  cnt > maxCount  THEN
      maxVal := val;
      maxCount := cnt
    END
  END;
  Out.String ("Longest sequence below ");       Out.Int (num, 1);
  Out.String (" is ");                          Out.Int (HailStone (maxVal, Count), 1);
  Out.String (" for n = ");                     Out.Int (maxVal, 1);
  Out.String (" with an intermediate maximum of ");
  Out.Int (HailStone (maxVal, Max), 1);
  Out.Ln
END FindMax;
 
BEGIN
  a := HailStone (27, List);
  Out.Ln;
  Out.String ("Iterations total = ");   Out.Int (HailStone (27, Count), 12);
  Out.String (" max value = ");         Out.Int (HailStone (27, Max)  , 12);
  Out.Ln;
  FindMax (1000000);
  Out.String ("Done.");
  Out.Ln
END hailst.