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


       identification division.
       program-id. hailstones.
       remarks. cobc -x hailstones.cob.
 
       data division.
       working-storage section.
       01 most                 constant as 1000000.
       01 coverage             constant as 100000.       
       01 stones               usage binary-long.
       01 n                    usage binary-long.
       01 storm                usage binary-long.
 
       01 show-arg             pic 9(6).
       01 show-default         pic 99 value 27.
       01 show-sequence        usage binary-long.
       01 longest              usage binary-long occurs 2 times.
 
       01 filler.
          05 hail              usage binary-long
                               occurs 0 to most depending on stones.
       01 show                 pic z(10).
       01 low-range            usage binary-long.
       01 high-range           usage binary-long.
       01 range                usage binary-long.
 
 
       01 remain               usage binary-long.
       01 unused               usage binary-long.
 
       procedure division.
       accept show-arg from command-line
       if show-arg less than 1 or greater than coverage then
           move show-default to show-arg
       end-if
       move show-arg to show-sequence
 
       move 1 to longest(1)
       perform hailstone varying storm
                         from 1 by 1 until storm > coverage
       display "Longest at: " longest(2) " with " longest(1) " elements"
       goback.
 
      *> **************************************************************
       hailstone.
       move 0 to stones
       move storm to n
       perform until n equal 1
           if stones > most then
               display "too many hailstones" upon syserr
               stop run
           end-if
 
           add 1 to stones
           move n to hail(stones)
           divide n by 2 giving unused remainder remain
           if remain equal 0 then
               divide 2 into n
           else
               compute n = 3 * n + 1
           end-if
       end-perform
       add 1 to stones
       move n to hail(stones)
 
       if stones > longest(1) then
           move stones to longest(1)
           move storm to longest(2)
       end-if
 
       if storm equal show-sequence then
           display show-sequence ": " with no advancing
           perform varying range from 1 by 1 until range > stones
               move 5 to low-range
               compute high-range = stones - 4
               if range < low-range or range > high-range then
                   move hail(range) to show
                   display function trim(show) with no advancing
                   if range < stones then
                       display ", " with no advancing
                   end-if
               end-if
               if range = low-range and stones > 8 then
                   display "..., " with no advancing
               end-if
           end-perform
           display ": " stones " elements"
       end-if
       .
 
       end program hailstones.