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).


 
>function hailstone (n) ...
$  v=[n];
$  repeat
$    if mod(n,2) then n=3*n+1;
$    else n=n/2;
$    endif;
$    v=v|n;
$    until n==1;
$  end;
$  return v;
$  endfunction
>hailstone(27), length(%)
 [ 27  82  41  124  62  31  94  47  142  71  214  107  322  161  484  242
 121  364  182  91  274  137  412  206  103  310  155  466  233  700
 350  175  526  263  790  395  1186  593  1780  890  445  1336  668
 334  167  502  251  754  377  1132  566  283  850  425  1276  638  319
 958  479  1438  719  2158  1079  3238  1619  4858  2429  7288  3644
 1822  911  2734  1367  4102  2051  6154  3077  9232  4616  2308  1154
 577  1732  866  433  1300  650  325  976  488  244  122  61  184  92
 46  23  70  35  106  53  160  80  40  20  10  5  16  8  4  2  1 ]
 112
>function hailstonelength (n) ...
$  v=zeros(1,n);
$  v[1]=4; v[2]=2;
$  loop 3 to n;
$    count=1;
$    n=#;
$    repeat
$      if mod(n,2) then n=3*n+1;
$      else n=n/2;
$      endif;
$      if n<=cols(v) and v[n] then 
$        v[#]=v[n]+count;
$        break;
$      endif;
$      count=count+1;    
$    end;
$  end;
$  return v;
$  endfunction
>h=hailstonelength(100000);
>ex=extrema(h); ex[3], ex[4]
 351
 77031
 