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.
Programming Praxis 
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)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); }And here’s a Perl flavor to display a Hailstone sequence.
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";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; } }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 ndef 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]
(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]
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 aThis 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."); } }Currently learning racket:
(define (seq n) (match n [1 '(1)] [_ (cons n (if (even? n) (seq (/ n 2)) (seq (+ (* 3 n) 1))))]))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];
}
}
}
var s = require('util').puts, n = 13; for(;n!=1;n=n&1?3*n+1:n/2,s(n+" "));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];
}
// just checking
Console.WriteLine("Hello world);
Caveat:
Oh my, the path length from 2,139,935,758 is apparently 2 — sometimes 32 bits (unsigned) isn’t enough.
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
PHP CLI:
<? $xi=$argv[1]; while($xi!=1) echo " ".$xi=$xi%2==0?$xi/2:3*$xi+1; ?>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:
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.
def hailstone_seq(x):
print x,
while x > 1:
if x % 2 == 0:
x = x/2
else:
x = 3*x + 1
print x,
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); } }