Hailstones

February 17, 2012

We have an easy exercise for a Friday afternoon.

Consider the sequence of positive integers for which xn+1 = xn / 2 when x is even and 3·xn + 1 when xn is odd; this is known colloquially as “half or triple plus one.” For instance, starting from x0 = 13 the sequence is 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, whence it loops through 4, 2, 1, …. This is called a hailstone sequence because it tends to go up and down and up and down much like hailstones in a thundercloud. Lothar Collatz conjectured in 1937 that every starting number eventually reaches 1; the conjecture is widely believed to be true, but has never been proven or disproven.

Your task is to write a function that computes hailstone sequences; you may wish to have some fun with your function by searching the internet for interesting tidbits about hailstone sequences and the Collatz conjecture. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

20 Responses to “Hailstones”

  1. DGel said

    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

    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

    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

    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

    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. 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. (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

    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

    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

    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

    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
    var s = require('util').puts, n = 13;
    for(;n!=1;n=n&1?3*n+1:n/2,s(n+" "));
    
  13. Joe Taylor said

    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


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

  15. Joe Taylor said

    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

    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

    PHP CLI:

    <?
    $xi=$argv[1];
    while($xi!=1)
            echo " ".$xi=$xi%2==0?$xi/2:3*$xi+1;
    ?>
    
  18. 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

    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

    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);
    	}
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 577 other followers

%d bloggers like this: