Programming Praxis

20 Responses to “Hailstones”

1. DGel said

   February 17, 2012 at 10:40 AM

   Trying to learn haskell, this seemed like it fits the language very well =) Had some problems figuring out type errors and precedence rules, but got it pretty soon.

   module Main where
   import System
   
   hailstones :: Integral a => a -> [a]
   hailstones 1 = [1]
   hailstones n
       | odd n = n : hailstones (3*n + 1)
       | even n = n : hailstones (n `div` 2)
   
   main = do
       n <- getArgs
       print . hailstones $ (read  (n !! 0) :: Integer)
   
2. Graham said

   February 17, 2012 at 12:23 PM

   I recently tried my hand at pulling this off in x86 Assembly; it didn’t go well. Since there’s already a Haskell version, here’s Python:

   #!/usr/bin/env python
   
   def hailstone(n):
       collatz = lambda n: 3 * n + 1 if n & 1 else n // 2
       hs = []
       while n != 1:
           hs.append(n)
           n = collatz(n)
       hs.append(1)
       return hs
   
   if __name__ == "__main__":
       from sys import argv
       print(hailstone(int(argv[1]) if len(argv)> 1 else 1729))
   

   And a more obfuscated C version (posted with the “cpp” sourcecode tag, hope it works):

   #include <stdio.h>
   #include <stdlib.h>
   
   int main(int argc, char **argv) {
       unsigned long n = argc > 1 ? atoi(argv[1]) : 1729;
       while (n != 1) printf("%lu\n", n = (n & 1) ? (n + (n << 1) + 1) : n >> 1);
   }
   
3. Paul G. said

   February 17, 2012 at 2:19 PM

   And here’s a Perl flavor to display a Hailstone sequence.

   #!/usr/bin/perl -w
   use strict;
   
   print my $n = $ARGV[0];
   print " " . ($n = ($n&1) ? 3*$n+1 : $n/2) while ($n > 1);
   

   I was rather surprised by how fast this works even for the large N. So, I tried figuring out the longest stop length also

   #!/usr/bin/perl -w
   use strict;
   
   my %longest = (4 => 3);
   for my $n (5 .. $ARGV[0]) {
       my $start = $n;
       my @list = ($n);
       push @list, ($n = ($n&1) ? 3*$n+1 : $n/2) while ( ($n > 1) && !exists($longest{$n}) );
       $longest{$start} = scalar(@list);
       $longest{$start} += $longest{$n}-1 if exists($longest{$start});
   }
   
   my $l = 4;
   foreach (keys %longest) {
       $l = $_ if ($longest{$_} > $longest{$l});
   }
   print "longest stop sequence is $longest{$l} for Hailstone($l)\n";
   
4. ardnew said

   February 17, 2012 at 9:53 PM

   darn, looks like Graham already beat me to the same solution

   #include <stdio.h>
   #include <inttypes.h>
   
   int main(int argc, char *argv[])
   {
     uintmax_t n;
     
     if (argc > 1 && (n = strtoumax(argv[1], 0, 0)) > 0)
     {
       printf("%ju\n", n);
       while (n >> 1)
         printf("%ju\n", n = n & 1 ? n + (n << 1 | 1) : n >> 1);
         
       return 0;
     }
     else
     {
       printf("\nusage:\n\t%s <START>\n\n", argv[0]);
       
       return 1;
     }
   }
   
5. Mike said

   February 17, 2012 at 11:10 PM

   My 2 cents:

   def hailstone_seq(n):
       """generator for hailstone sequence starting at n
   
       >>>list(hailstone_seq(13))
       [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
       """"
       yield n
       while n != 1:
           n = (3*n + 1) if n&1 else (n//2)
           yield n
   
   
6. Rubén Barroso said

   February 18, 2012 at 12:05 AM

   def hailstone(x):
   “”” A wondrous number is one which eventually reaches 1 using this function.
   See GEB pages 400 and 401. “””
   seq = [x]
   while x != 1:
   # how I miss tail-call optimization in Python
   if not x % 2:
   x /= 2
   else:
   x = 3 * x + 1
   seq.append(x)
   return seq

   # Test
   print hailstone(15)

   # Output
   # [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
7. Rubén Barroso said

   February 18, 2012 at 12:07 AM

   (Bad formatting above, damn. Now better)

   def hailstone(x):
   """ A wondrous number is one which eventually reaches 1 using this function.
   See GEB pages 400 and 401. """
   seq = [x]
   while x != 1:
   # how I miss tail-call optimization in Python
   if not x % 2:
   x /= 2
   else:
   x = 3 * x + 1
   seq.append(x)
   return seq

   # Test
   print hailstone(15)

   # Output
   # [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
8. slabounty said

   February 18, 2012 at 11:59 PM

   In ruby …

   def hailstone(n)
       begin
           yield n
           n = n % 2 == 1 ? 3*n+1 : n/2
       end while n != 1
       yield n
   end
   
   a = []
   hailstone(13) { |n| a << n }
   p a
   
9. Eugene said

   February 19, 2012 at 4:50 AM

   This was a rather simple program to solve in Java.

   package hailstones;
   import java.util.Scanner;
   
   public class Hailstones {
   
       public static void main(String[] args) {
           int num1;  //Input variable.
           int count = 0;
           Scanner scan = new Scanner(System.in);
           
           System.out.println("We are going to be running a sequence!");
           System.out.println("Please enter your first number: ");
           num1 = scan.nextInt();
           
           while(num1 != 1)
           {
               if(num1%2 == 0)
               {
                   num1 = num1/2;
               }
               
               else{
                   num1 = (3*num1)+1;
               }
               
               count++;
               System.out.println(num1);
           }
           
           System.out.println("There were "+count+" elements in the sequence.");
       }
   }
   
   
10. Mike said

    February 19, 2012 at 3:21 PM

    Currently learning racket:

    
    (define (seq n)
      (match n 
        [1 '(1)]
        [_ (cons n (if (even? n) 
                        (seq (/ n 2))
                        (seq (+ (* 3 n) 1))))]))
    
    
11. Joe Taylor said

    February 20, 2012 at 11:19 PM

    I wass interested in developing a count for the number of items in a sequence for some set of numbers, e.g.:
    1 => 1, length 1
    2 => 2, 1, length 2
    3 => 3, 16, 8, 4, 2, 1, length = 6
    4 => 4, 2, 1, length = 3
    etc.

    The problem seemed to scream “recursion”, and so it can be solved… up to a point, depending on your resources: this code runs in roughly 400ms on a particularly beefy 64-bit desktop with 16GB RAM and quad core, .Net 4.0
    I’m going to see about being a bit less recursive but still performant:
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    using System.Text;

    namespace Hailstone
    {
    class Program
    {
    static void Main(string[] args)
    {
    var maxValue = 100000;
    IDictionary stones = new SortedDictionary();
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    //Enumerable.Range(1, maxValue).AsParallel().ForAll(i =>
    // {
    // _stones[i] = Hail(i);
    // });

    foreach (var i in Enumerable.Range(1, maxValue))
    {
    if (!stones.ContainsKey(i))
    {
    stones[i] = Hail(i, stones);
    }
    }

    var byValue = stones.OrderBy(kv => kv.Value).ToDictionary(kv => kv.Key, kv=>kv.Value);
    stopwatch.Stop();
    Console.WriteLine(stopwatch.Elapsed);
    }

    static private int Hail(int x, IDictionary stones)
    {
    if (x == 1)
    {
    stones[x] = x;
    }
    else if (!stones.ContainsKey(x))
    {
    stones[x] = (x % 2 == 0) ?
    1 + Hail(x >> 1, stones) :
    1 + Hail(x*3 + 1, stones);
    }
    return stones[x];
    }
    }
    }
12. Alec Gorge said

    February 21, 2012 at 3:09 AM

    var s = require('util').puts, n = 13;
    for(;n!=1;n=n&1?3*n+1:n/2,s(n+" "));
    
13. Joe Taylor said

    February 21, 2012 at 3:12 PM

    OK, so now I have two versions, the recursive, which will very quickly lead to resource abuse, and a non-recursive, which does a little bit less so. Was able to determine paths for fourch 2.1 * 10^6 elements in 4.5 seconds on my seemingly beefy desktop.
    [Apologies for the lack of code style]

    static private int Hail(int x, IDictionary stones)
    {
    int result = 0;
    var trail = new Stack();
    while(x > 0)
    {
    if (stones.ContainsKey(x))
    {
    result = stones[x];
    break;
    }
    else if (x > 1)
    {
    trail.Push(x);
    x = (x%2) == 0 ? x >> 1 : x*3 + 1;
    }
    else // x = 1
    {
    result = stones[x] = 1;
    break;
    }
    }

    while(trail.Count > 0)
    {
    var key = trail.Pop();
    stones[key] = ++result;
    }

    return result;

    }

    static private int RecursiveHail(int x, IDictionary stones)
    {
    if (x == 1)
    {
    stones[x] = 1;
    }
    else if (!stones.ContainsKey(x))
    {
    stones[x] = (x % 2 == 0) ?
    1 + Hail(x >> 1, stones) :
    1 + Hail(x * 3 + 1, stones);
    }
    return stones[x];
    }
14. Joe Taylor said

    February 21, 2012 at 3:16 PM

    
// just checking
Console.WriteLine("Hello world);

15. Joe Taylor said

    February 21, 2012 at 3:45 PM

    Caveat:
    Oh my, the path length from 2,139,935,758 is apparently 2 — sometimes 32 bits (unsigned) isn’t enough.
16. Shankar Chakkere said

    February 22, 2012 at 4:48 AM

    In Apple I BASIC on Mac OS X (http://www.pagetable.com/?p=35)

    #!/usr/bin/apple1basic
    1 REM February 21, 2012 11:25 PM
    100 PRINT “ENTER THE NUMBER”
    200 INPUT N
    300 PRINT N
    310 IF N = 1 THEN END
    410 IF (N/2)*2 = N THEN GOTO 600
    500 REM EVEN NUMBER
    510 N = 3 * N +1
    530 GOTO 300
    600 REM ODD NUMBER
    610 N = N /2
    630 GOTO 300
    900 END

    new-host-4:Apple BASIC shankara_c$ apple1basic hailstone.bas
    ENTER THE NUMBER
    ?13
    13
    40
    20
    10
    5
    16
    8
    4
    2
    1
17. Manoj Senguttuvan said

    February 23, 2012 at 9:08 AM

    PHP CLI:

    <?
    $xi=$argv[1];
    while($xi!=1)
            echo " ".$xi=$xi%2==0?$xi/2:3*$xi+1;
    ?>
    
18. Elvis Montero said

    February 27, 2012 at 6:54 PM

    This problem lends itself to a recursive solution. Here’s a Javascript snippet exemplifying this fact:

    var hailstone = function(n){      
        if(n === 1)
            return "";    
        
        var cycle = "";
        
        if(n % 2 === 0){
            cycle += (n / 2) + " " + hailstone(n / 2);
        }
        else{
            cycle += (3 * n + 1) + " " + hailstone(3 * n + 1);
        }
        
        return cycle;
    };
    
    console.log(hailstone(13));
    console.log(hailstone(25));
    console.log(hailstone(600));
    

    And here’s the output:

    40 20 10 5 16 8 4 2 1 
    76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
    300 150 75 226 113 340 170 85 256 128 64 32 16 8 4 2 1 
    

    I’m not using memoization or any other cache mechanism, which would allow us to compute larger sequences faster, because I feel that mars the simplicity of the code. Of course, if speed and space were of any real consequence, then that’s an approach that’d have to be explored.
19. Supriya said

    March 1, 2012 at 7:22 AM

    def hailstone_seq(x):
    print x,
    while x > 1:
    if x % 2 == 0:
    x = x/2
    else:
    x = 3*x + 1
    print x,
20. Sam Kennedy said

    June 8, 2012 at 9:41 PM

    This is what I made, I want to try and make a fractal but don’t know enough about complex numbers.. I’ll see what I end up with :)

    using namespace std;
    
    int Collatz(int start);
    
    int main(){
    	int i;
    	cout << "Enter Starting Number: ";
    	cin >> i;
    	Collatz(i);
    	system("pause");
    	return 0;
    }
    
    int Collatz(int start){
    	cout << start << " ";
    	if(start == 1){
    		cout << endl;
    		return 1;
    	}
    	if(start % 2 == 0){
    		Collatz(start/2);
    	}
    	else
    	{
    		Collatz((3*start)+1);
    	}
    }