Hailstone sequence

Hailstone sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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.

The task is to:

1. Create a routine to generate the hailstone sequence for a number.
2. 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
3. Show the number less than 100,000 which has the longest hailstone sequence together with that sequences length.
   (But don't show the actual sequence)!

Clojure

<lang clojure>(defn hailstone-seq [n]

 (:pre [(pos? n)])
 (lazy-seq 
  (cond (= n 1)   '(1)
        (even? n) (cons n (hailstone-seq (/ n 2)))
        :else     (cons n (hailstone-seq (+ (* n 3) 1))))))

(def hseq27 (hailstone-seq 27)) (assert (= (count hseq27) 112)) (assert (= (take 4 hseq27) [27 82 41 124])) (assert (= (drop 108 hseq27) [8 4 2 1]))

(let [{max-i :num, max-len :len}

     (reduce #(max-key :len %1 %2)
             (for [i (range 1 100000)]
               {:num i, :len (count (hailstone-seq i))}))]
 (println "Maximum length" max-len "was found for hailstone(" max-i ")."))</lang>

Forth

<lang forth>: hail-next ( n -- n )

 dup 1 and if 3 * 1+ else 2/ then ;

.hail ( n -- )

 begin dup . dup 1 > while hail-next repeat drop ;

hail-len ( n -- n )

 1 begin over 1 > while swap hail-next swap 1+ repeat nip ;

27 hail-len . cr 27 .hail cr

longest-hail ( max -- )

 0 0 rot 1+ 1 do    ( n length )
   i hail-len 2dup < if
     nip nip i swap
   else drop then
 loop
 swap . ." has hailstone sequence length " . ;

100000 longest-hail</lang>

Logo

<lang logo>to hail.next :n

 output ifelse equal? 0 modulo :n 2 [:n/2] [3*:n + 1]

end

to hail.seq :n

 if :n = 1 [output [1]]
 output fput :n hail.seq hail.next :n

end

show hail.seq 27 show count hail.seq 27

to max.hail :n

 localmake "max.n 0
 localmake "max.length 0
 repeat :n [if greater? count hail.seq repcount  :max.length [
   make "max.n repcount
   make "max.length count hail.seq repcount
 ] ]
 (print :max.n [has hailstone sequence length] :max.length)

end

max.hail 100000</lang>

Oz

<lang oz>declare

 fun {HailstoneSeq N}
    N > 0 = true %% assert
    if N == 1 then         [1]
    elseif {IsEven N} then N|{HailstoneSeq N div 2}
    else                   N|{HailstoneSeq 3*N+1}
    end
 end

 HSeq27 = {HailstoneSeq 27}
 {Length HSeq27} = 112
 {List.take HSeq27 4} = [27 82 41 124]
 {List.drop HSeq27 108} = [8 4 2 1]

 fun {MaxBy2nd A=A1#A2 B=B1#B2}
    if B2 > A2 then B else A end
 end

 Pairs = {Map {List.number 1 99999 1}
          fun {$ I} I#{Length {HailstoneSeq I}} end}

 MaxI#MaxLen = {List.foldL Pairs MaxBy2nd 0#0}
 {System.showInfo
  "Maximum length "#MaxLen#" was found for hailstone("#MaxI#")"}</lang>
 

Output:

Maximum length 351 was found for hailstone(77031)

PureBasic

When compiled For Windows x86 using PureBasic 4.41 , this code is only 7 kB.

<lang PureBasic>NewList Hailstones.i() ; Make a linked list to use as we do not know the numbers of elements needed for an Array

Procedure.i FillHailstones(n) ; Fills the list & returns the amount of elements in the list

 Shared Hailstones()         ; Get access to the Hailstones-List
 ClearList(Hailstones())     ; Remove old data
 Repeat
   AddElement(Hailstones())  ; Add an element to the list
   Hailstones()=n            ; Fill current value in the new list element
   If n=1
     ProcedureReturn ListSize(Hailstones())
   ElseIf n%2=0
     n/2
   Else
     n=(3*n)+1
   EndIf
 ForEver

EndProcedure

If OpenConsole()

 Define i, l, maxl, maxi
 l=FillHailstones(27)
 Print("#27 has "+Str(l)+" elements and the sequence is: "+#CRLF$)
 ForEach Hailstones()
   If i=6
     Print(#CRLF$)
     i=0
   EndIf    
   i+1
   Print(RSet(Str(Hailstones()),5))
   If Hailstones()<>1
     Print(", ")
   EndIf
 Next
 
 i=1
 Repeat
   l=FillHailstones(i)
   If l>maxl
     maxl=l
     maxi=i
   EndIf
   i+1
 Until i>=100000
 Print(#CRLF$+#CRLF$+"The longest sequence below 100000 is #"+Str(maxi)+", and it has "+Str(maxl)+" elements.")

 Print(#CRLF$+#CRLF$+"Press ENTER to exit."): Input()
 CloseConsole()

EndIf</lang>

Output

#27 has 112 elements and the sequence is:
   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

The longest sequence found up to 100000 is #77031 which has 351 elements.

Press ENTER to exit.

Python

<lang python>def hailstone(n):

   seq = [n]
   while n>1:
       n = 3*n + 1 if n & 1 else n//2
       seq.append(n)
   return seq

if __name__ == '__main__':

   h = hailstone(27)
   assert len(h)==112 and h[:4]==[27, 82, 41, 124] and h[-4:]==[8, 4, 2, 1]
   print("Maximum length %i was found for hailstone(%i) for numbers <100,000" %
         max((len(hailstone(i)), i) for i in range(1,100000)))</lang>

Sample Output

Maximum length 351 was found for hailstone(77031) for numbers <100,000

Tcl

The core looping structure is an example of an n-plus-one-half loop, except the loop is officially infinite here. <lang tcl>proc hailstone n {

   while 1 {

lappend seq $n if {$n == 1} {return $seq} set n [expr {$n & 1 ? $n*3+1 : $n/2}]

   }

}

set h27 [hailstone 27] puts "h27 len=[llength $h27]" puts "head4 = [lrange $h27 0 3]" puts "tail4 = [lrange $h27 end-3 end]"

set maxlen [set max 0] for {set i 1} {$i<100000} {incr i} {

   set l [llength [hailstone $i]]
   if {$l>$maxlen} {set maxlen $l;set max $i}

} puts "max is $max, with length $maxlen"</lang> Output:

h27 len=112
head4 = 27 82 41 124
tail4 = 8 4 2 1
max is 77031, with length 351