Hailstone sequence: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:27, 11 March 2010

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 with 8, 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>

C

<lang C>#include <stdio.h>

include <stdlib.h>

int hailstone(int n, int *arry) {

   int hs = 1;

   while (n!=1) {
       hs++;
       if (arry) *arry++ = n;
       n = (n&1) ? (3*n+1) : (n/2);
   }
   if (arry) *arry++ = n;
   return hs;

}

int main() {

   int j, hmax = 0;
   int jatmax, n;
   int *arry;

   for (j=1; j<100000; j++) {
      n = hailstone(j, NULL);
      if (hmax < n) {
          hmax = n;
          jatmax = j;
      }
   }
   n = hailstone(27, NULL);
   arry = (int *)malloc(n*sizeof(int));
   n = hailstone(27, arry);

   printf("[ %d, %d, %d, %d, ...., %d, %d, %d, %d] len=%d\n",
       arry[0],arry[1],arry[2],arry[3],
       arry[n-4], arry[n-3], arry[n-2], arry[n-1], n);
   printf("Max %d at j= %d\n", hmax, jatmax);
   free(arry);

   return 0;

}</lang> Output

[ 27, 82, 41, 124, ...., 8, 4, 2, 1] len= 112
Max 351 at j= 77031

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>

FALSE

<lang false>[$1&$[%3*1+0~]?~[2/]?]n: [[$." "$1>][n;!]#%]s: [1\[$1>][\1+\n;!]#%]c: 27s;! 27c;!." " 0m:0f: 1[$100000\>][$c;!$m;>[m:$f:0]?%1+]#% f;." has hailstone sequence length "m;.</lang>

Java

Works with: Java version 1.5+

<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

(* 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)

PL/I

This example is incorrect. Please fix the code and remove this message.

Details: Only the first part of the task is attempted.
-- I know that. It was too long to do all at once online. -- More added. --

<lang PL/I> test: proc options (main);

  declare (longest, n) fixed (15);
  declare flag bit (1);
  declare (i, value) fixed (15);

  /* Task 1: */
  flag = '1'b;
  put skip list ('The sequence for 27 is');
  i = hailstones(27);

  /* Task 2: */
  flag = '0'b;
  longest = 0;
  do i = 1 to 99999;
     if longest < hailstones(i) then
        do; longest = hailstones(i); value = i; end;
  end;
  put skip edit (value, ' has the longest sequence of ', longest) (a);

hailstones: procedure (n) returns ( fixed (15));

  declare n fixed (15) nonassignable;
  declare (m, p) fixed (15);

  m = n;
  p = 1;
  if flag then put skip list (m);
  do p = 1 by 1 while (m > 1);
     if iand(m, 1) = 0 then
        m = m/2;
     else
        m = 3*m + 1;
     if flag then put skip list (m);
  end;
  if flag then put skip list ('The hailstone sequence has length' || p);
  return (p);

end hailstones;

end test; </lang> Output: <lang> The sequence for 27 is

The hailstone sequence has length 112

            77031 has the longest sequence of                351

</lang>

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

Hailstone sequence: Difference between revisions

Revision as of 12:27, 11 March 2010

AutoHotkey

C

Clojure

FALSE

Forth

Java

Logo

OCaml

Oz

PL/I

PureBasic

Python

Tcl