Hailstone sequence
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
You are encouraged to solve this task according to the task description, using any language you may know.
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)!
AutoHotkey
<lang autohotkey>; Submitted by MasterFocus - http://tiny.cc/iTunis
- [1] Generate the Hailstone Seq. for a number
List := varNum := 7 ; starting number is 7, not counting elements While ( varNum > 1 )
List .= ", " ( varNum := ( Mod(varNum,2) ? (varNum*3)+1 : varNum//2 ) )
MsgBox % List
- [2] Seq. for starting number 27 has 112 elements
Count := 1, List := varNum := 27 ; starting number is 27, counting elements While ( varNum > 1 )
Count++ , List .= ", " ( varNum := ( Mod(varNum,2) ? (varNum*3)+1 : varNum//2 ) )
MsgBox % "Sequence:`n" List "`n`nCount: " Count
- [3] Find number<100000 with longest seq. and show both values
MaxNum := Max := 0 ; reset the Maximum variables TimesToLoop := 100000 ; limit number here is 100000 Offset := 70000 ; offset - use 0 to process from 0 to 100000 Loop, %TimesToLoop% {
If ( TimesToLoop < ( varNum := Index := A_Index+Offset ) ) Break text := "Processing...`n-------------------`n" text .= "Current starting number: " Index "`n" text .= "Current sequence count: " Count text .= "`n-------------------`n" text .= "Maximum starting number: " MaxNum "`n" text .= "Maximum sequence count: " Max " <<" ; text split to avoid long code lines ToolTip, %text% Count := 1 ; going to count the elements, but no "List" required While ( varNum > 1 ) Count++ , varNum := ( Mod(varNum,2) ? (varNum*3)+1 : varNum//2 ) If ( Count > Max ) Max := Count , MaxNum := Index ; set the new maximum values, if necessary
} ToolTip MsgBox % "Number: " MaxNum "`nCount: " Max</lang>
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>
OCaml
<lang ocaml>
- load "nums.cma";;
open Num;;
(* generate Hailstone sequence *) let hailstone n = let one = num_of_int 1 and two = num_of_int 2 and three = num_of_int 3 in let rec g s x = if x =/ one then x::s else g (x::s) (if mod_num x two =/ one then three */ x +/ one else x // two) in g [ ] (num_of_int n);;
(* compute only sequence length *) let haillen n = let one = num_of_int 1 and two = num_of_int 2 and three = num_of_int 3 in let rec g s x = if x =/ one then s+1 else g (s+1) (if mod_num x two =/ one then three */ x +/ one else x // two) in g 0 (num_of_int n);;
(* max length for starting values in 1..n *) let hailmax = let rec g idx len = function 0 -> (idx, len) | i -> let a = haillen i in if a > len then g i a (i-1) else g idx len (i-1) in g 0 0;;
hailmax 100000;; (* - : int * int = (77031, 351) *)
List.rev_map string_of_num (hailstone 27);;
(* - : string list = ["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"] *)</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