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


 
CLASS lcl_hailstone DEFINITION.
  PUBLIC SECTION.
    TYPES: tty_sequence TYPE STANDARD TABLE OF i
                             WITH NON-UNIQUE EMPTY KEY,
           BEGIN OF ty_seq_len,
             start TYPE i,
             len   TYPE i,
           END OF ty_seq_len,
           tty_seq_len TYPE HASHED TABLE OF ty_seq_len
                            WITH UNIQUE KEY start.
 
    CLASS-METHODS:
      get_next
        IMPORTING
          n                           TYPE i
        RETURNING
          VALUE(r_next_hailstone_num) TYPE i,
 
      get_sequence
        IMPORTING
          start             TYPE i
        RETURNING
          VALUE(r_sequence) TYPE tty_sequence,
 
      get_longest_sequence_upto
        IMPORTING
          limit                     TYPE i
        RETURNING
          VALUE(r_longest_sequence) TYPE ty_seq_len.
 
  PRIVATE SECTION.
    TYPES: BEGIN OF ty_seq,
             start TYPE i,
             seq   TYPE tty_sequence,
           END OF ty_seq.
    CLASS-DATA: sequence_buffer TYPE HASHED TABLE OF ty_seq
                                     WITH UNIQUE KEY start.
ENDCLASS.
 
CLASS lcl_hailstone IMPLEMENTATION.
  METHOD get_next.
    r_next_hailstone_num = COND #( WHEN n MOD 2 = 0 THEN n / 2
                                   ELSE ( 3 * n ) + 1 ).
  ENDMETHOD.
 
  METHOD get_sequence.
    INSERT start INTO TABLE r_sequence.
    IF start = 1.
      RETURN.
    ENDIF.
 
    READ TABLE sequence_buffer ASSIGNING FIELD-SYMBOL(<buff>)
                               WITH TABLE KEY start = start.
    IF sy-subrc = 0.
      INSERT LINES OF <buff>-seq INTO TABLE r_sequence.
    ELSE.
      DATA(seq) = get_sequence( get_next( start ) ).
      INSERT LINES OF seq INTO TABLE r_sequence.
      INSERT VALUE ty_seq( start = start
                           seq   = seq ) INTO TABLE sequence_buffer.
    ENDIF.
  ENDMETHOD.
 
  METHOD get_longest_sequence_upto.
    DATA: max_seq TYPE ty_seq_len,
          act_seq TYPE ty_seq_len.
 
    DO limit TIMES.
      act_seq-len = lines( get_sequence( sy-index ) ).
 
      IF act_seq-len > max_seq-len.
        max_seq-len   = act_seq-len.
        max_seq-start = sy-index.
      ENDIF.
    ENDDO.
 
    r_longest_sequence = max_seq.
  ENDMETHOD.
ENDCLASS.
 
START-OF-SELECTION.
  cl_demo_output=>begin_section( |Hailstone sequence of 27 is: | ).
  cl_demo_output=>write( REDUCE string( INIT result = ``
                                        FOR item IN lcl_hailstone=>get_sequence( 27 )
                                        NEXT result = |{ result } { item }| ) ).
  cl_demo_output=>write( |With length: { lines( lcl_hailstone=>get_sequence( 27 ) ) }| ).
  cl_demo_output=>begin_section( |Longest hailstone sequence upto 100k| ).
  cl_demo_output=>write( lcl_hailstone=>get_longest_sequence_upto( 100000 ) ).
  cl_demo_output=>display( ).
 