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