Saturday, February 14, 2009
Hamming numbers
The set of Hamming numbers H is defined recursively. 1 is in H. The numbers 2h, 3h, 5h are in H, if h is a number contained in H. The first few hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, ... Dijkstra put the problem of computing efficiently the hamming numbers. What is your proposal?
Subscribe to:
Post Comments (Atom)
A first naive solution is to start with the set H_0 = {1, 2, 3, 5 } then build H_i = 3 * h_{i-1}, h_{i-1} \in H_{i-1}, i>0. Obviously, we generate multiple duplicates that we can t"eliminate" with a post-processing sort operation.
ReplyDeleteWhat is wrong with that?