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

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 = 
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) 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) : 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;
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) {
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, 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);

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!");
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;
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);
}
}
```