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


begin
    % show some Hailstone Sequence related information                       %
    % calculates the length of the sequence generated by n,                  %
    % if showFirstAndLast is true, the first and last 4 elements of the      %
    % sequence are stored in first and last                                  %
    % hs holds a cache of the upbHs previously calculated sequence lengths   %
    % if showFirstAndLast is false, the cache will be used                   %
    procedure hailstone ( integer value  n
                        ; integer array  first, last ( * )
                        ; integer result length
                        ; integer array  hs          ( * )
                        ; integer value  upbHs
                        ; logical value  showFirstAndLast
                        ) ;
    if not showFirstAndLast and n <= upbHs and hs( n ) not = 0 then begin
        % no need to store the start and end of the sequence and we already  %
        % know the length of the sequence for n                              %
        length := hs( n )
        end
    else begin
        % must calculate the sequence length                                 %
        integer sv;
        for i := 1 until 4 do first( i ) := last( i ) := 0;
        length := 0;
        sv     := n;
        if sv > 0 then begin
            while begin
                length := length + 1;
                if showFirstAndLast then begin
                    if length <= 4 then first( length ) := sv;
                    for lPos := 1 until 3 do last( lPos ) := last( lPos + 1 );
                    last( 4 ) := sv
                    end
                else if sv <= upbHs and hs( sv ) not = 0 then begin
                    % have a known value                                 %
                    length := ( length + hs( sv ) ) - 1;
                    sv     := 1
                end ;
                sv not = 1
            end do begin
                sv := if odd( sv ) then ( 3 * sv ) + 1 else sv div 2
            end while_sv_ne_1 ;
            if n < upbHs then hs( n ) := length
        end if_sv_gt_0
    end hailstone ;
    begin
        % test the hailstone procedure                                       %
        integer HS_CACHE_SIZE;
        HS_CACHE_SIZE := 100000;
        begin
            integer array first, last ( 1 :: 4 );
            integer       length, maxLength, maxNumber;
            integer array hs          ( 1 :: HS_CACHE_SIZE );
            for i := 1 until HS_CACHE_SIZE do hs( i ) := 0;
            hailstone( 27, first, last, length, hs, HS_CACHE_SIZE, true );
            write( i_w := 1, s_w := 0
                 , "27: length ", length, ", first: ["
                 , first( 1 ), " ", first( 2 ), " ", first( 3 ), " ", first( 4 )
                 , "] last: ["
                 , last( 1 ), " ", last( 2 ), " ", last( 3 ), " ", last( 4 )
                 , "]"
                 );
            maxNumber := 0;
            maxLength := 0;
            for n := 1 until 100000 do begin
                hailstone( n, first, last, length, hs, HS_CACHE_SIZE, false );
                if length > maxLength then begin
                    maxNumber := n;
                    maxLength := length
                end if_length_gt_maxLength
            end for_n ;
            write( i_w := 1, s_w := 1, "Maximum sequence length: ", maxLength, " for: ", maxNumber )
        end
    end
end.