## Hamming Numbers

### August 30, 2011

The sequence of Hamming numbers 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, … (A051037) consists of all numbers of the form 2^{i}·3^{j}·5^{k} where *i*, *j* and *k* are non-negative integers. Edsger Dijkstra introduced this sequence to computer science in his book *A Discipline of Programming*, and it has been a staple of beginning programming courses ever since. Dijkstra wrote a program based on three axioms:

Axiom 1: The value 1 is in the sequence.

Axiom 2: If

xis in the sequence, so are 2 *x, 3 *x, and 5 *x.Axiom 3: The sequence contains no other values other than those that belong to it on account of Axioms 1 and 2.

.

Your task is to write a program to compute the first thousand terms of the Hamming sequence. 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

I wrote a Haskell version of Python’s test of using lazy evaluation to generate them; as it turns out, it’s the same as the SRFI-41 version.

Since I’m new to Haskell, I probably didn’t find the most elegant solution (and suggestions are welcome), but lazy evaluation is kind of amazing.

Looks like I had some redundant parentheses in my definition of merge, according to hlint. Apologies.

Re the imperative version, I think it is nicer to omit the 0 that does not belong to the sequence and simply produce a 0-based sequence of n elements:

(Cut-and-paste from my editor window to be safer against silly typos. I called my translation of Dijkstra’s code aq.)

Jussi: I tend to add a useless element to the beginning of arrays when porting code from languages that base arrays at 1 instead of 0. It’s mostly harmless, and saves a lot of x+1 and x-1 statements mapping between the two formats. I agree it’s ugly, but only a little bit. Where it actually matters, I do it right.

Here’s a shortish but quite efficient lazy Clojure version:

(defn hammings [initial-set]

(let [v (first initial-set)

others (rest initial-set)]

(lazy-seq

(cons

v

(hammings (into (sorted-set (* v 2) (* v 3) (* v 5)) others))))))

(take 1000 (hammings #{1}))

Runs in about 0.07 ms for the first 1000 hamming numbers on my machine.

Here’s my clojure solution. More details at my blog.

hemming = [1] ++ concatMap (\ x -> [x*2, x*3, x*5]) hemming

first1k = sort . take 1000 $ hemming

My Haskell variant

Dijkstra advocated 0-based indexing, so I think his algorithm in the chapter may actually be intended to be 0-based. It is hard to tell for sure. However, his initialization of aq to (1 1) is funny either way when only one 1 is meant to remain in the result, and the assignments to ik, xk seem to need to be either parallel or swapped when I implement it. Below is a 0-based version with parallel assignments. For example, (set*! (x y) y x) swaps x and y. (Originally I had tail-recursion instead of assignments, and I did not even notice that the second assignments in Dijkstra depend on the first ones.)

Cheers.

@Philipp: I like the brevity of your Haskell answer, but it seems to include a lot of repeats; as a Haskell newbie, I couldn’t figure out a way to remove them easily. Any ideas?

nub

Continuing to attempt to become more familiar with Haskell. Here is what I came up with.

In case you’re curious, my solution is in Lazy Racket :-)

Ended up playing with my answer some more while waiting for some other code to compile. I like how this one better.

HammingNumbers.java

hamm.go

@programmingpraxis: I’ve tried throwing

`nub`

into the solution, but it either (1) comes after`take 1000`

, in which case there are no longer 1000 entries, or (2) comes before it, and the program just hangs. I am not very adept in Haskell :-(Hamming number generator in Python 3.

Follows directly from the definition. Yield 1, then yield 2*, 3* and 5* a number in the list. It’s lazy too.

from heapq import merge

from itertools import tee

def hamming_numbers():

last = 1

yield last

a,b,c = tee(hamming_numbers(), 3)

for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)):

if n != last:

yield n

last = n

x = list(islice(hamming_numbers(),1000))

print(x[:10], x[-5:])

# output -> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] [50331648, 50388480, 50625000, 51018336, 51200000]

This time with proper formating:

Nothing magical here…

Inelegant but fast to write in Python:

my C++ solution. I’m disappointed that it takes so long for my implementation to calculate the sequence. (especially since someone got it in less thana tenth of a second.)Can someone tell me where I can improve the code?

http://codepad.org/WhHDxJAZ

The suggested solution makes

ntrips through a single loop, at each iteration calculating a minimum of three integers, performing three`if`

tests comparing two integers at each iteration, and making a single addition and a single multiplication.Your code has 5

`for`

loops, two of them with`if`

tests inside them, and 1`while`

loop containing an`if`

which has a nested`if`

inside it. And the inner loop of your code performs a`modulo`

operation (a very expensive operation) and a compare for`divisorSize`

×`sequenceIndex`

iterations.And you forgot the 1 that starts the sequence.

By the way, the suggested solution runs in a thousandth of a second, not a tenth of a second:

`> (define x #f)`

> (time (set! x (hamming 1000)))

(time (set! x ...))

no collections

1 ms elapsed cpu time

1 ms elapsed real time

12048 bytes allocated

> (vector-ref x 1000)

51200000

To improve your code, you should follow the suggested solution.

I’m sorry if that’s a little bit harsh. I’ll be happy to look at your improved solution.

Phil

[...] compute the first thousand terms of the Hamming sequence. 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 [...]

[...] This question is copyright of programmingpraxis.com. Click here to see the original [...]

Here is my C implementation!

http://codepad.org/ilubfEfd

Thanks Phil for a review of my code. I now see how inefficient it is and was working on a revision but I don’t think I can make my algorithm as efficient as Supriya Koduri’s, to whom I want to ask “what train of thought allowed him to create such an elegant solution?”.

ruby solution : http://codepad.org/b87tK8qQ

Another solution based upon Dijkstra’s paper:

cosmin’s solution in Go: http://play.golang.org/p/qD1Tqntcy5

The results of the cosmin’s solution in Go posted by glnbrwn 12Dec2012 in Go do not match.

Python version posted October 30, 2012 by cosmin results are:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, …

Go when executed at the link given above results in:

[1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64

Go is missing 10, 15, 20, 25, 30 when executing it. Multiples of 5 are not getting added to the result.