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:
- 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 with8, 4, 2, 1
- 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>
Java
<lang java5>import java.util.LinkedList;
public class Hailstone {
public static void main(String[] args) { System.out.println(hailstone(27)); int len = 0; int num = 1; for (int i = 1; i < 100000; i++) { LinkedList<Long> hail = hailstone(i); if (hail.size() > len) { len = hail.size(); num = i; } } System.out.println("Longest sequence at n = " + num + " with length " + len); }
public static LinkedList<Long> hailstone(long n) { LinkedList<Long> ans = new LinkedList<Long>(); ans.add(n); if (n == 1) { return ans; } if (n % 2 == 0) { ans.addAll(hailstone(n / 2)); } else { ans.addAll(hailstone(n * 3 + 1)); } return ans; }
}</lang> Output:
[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] Longest sequence at n = 77031 with length 351
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