A Hamming Number [named after R. W. Hamming, who first discussed this exercise] is a positive integer which has no prime factor other than 2, 3 and 5; for example, 60 = 2 × 2 × 3 × 5 is such a number, but 42 [which is divisible by 7] isn't. Hamming's Problem is to find the first so-many [say, 1000] Hamming numbers.
At first, there are lots of Hamming numbers: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, .... Later, there aren't quite so many: 80, 90, 96, 100, 108, 120, ...; and then they get really quite few and far between [for example, since the largest power of 2 below 10^10 is 33, of 3 is 20 and of 5 is 14, there are fewer than 34 × 21 × 15 = 10710 Hamming numbers below 10^10, so fewer than about one in a million numbers are Hamming in this range].
Testing to see if a number is Hamming is pretty easy: divide by 2 as long as you can, then by 3, then by 5, and the number is Hamming if the answer is 1, and not otherwise. So one possible algorithm is to start at 1, count upwards, testing each number to see if it's Hamming, and stop when you have enough.
Exercise 1: Sketch a computer program for this. Don't spend too long!But the above analysis shows that this will take too long. So we need a more constructive way of finding the numbers. Part of this is easy. We can define the Hamming numbers alternatively by the following:
So we can take any old collection of Hamming numbers, multiply them by 2, 3 or 5 as we see fit, and generate as many more as we like. But how will we know we haven't missed some? We obviously need to be systematic, and generate them in the right order. We must keep a collection of `Hamming numbers so far', starting with the first Hamming number, 1, and we must generate the `next' number to add to our collection. So we have the germ of an algorithm:
- 1 is a Hamming number;
- if H is a Hamming number, then so are 2 × H, 3 × H and 5 × H; and
- there are no other Hamming numbers.
Declare an array big enough for the whole collection
Put 1 into the collection, and set n = 1
While n < number_desired
Find the next Hamming number,
Add it to the collection,
Increment n.
To find the next number:
Take 2× the number at the 2-finger,
Take 3× the number at the 3-finger,
Take 5× the number at the 5-finger,
Choose the smallest of these three numbers,
Update the fingers.
Exercise 2: Turn this into a sketch of a complete program for this problem.If, after all this, you need a full solution, look in the semi-recommended book by Dijkstra.
Footnote: Of course, no-one is really that interested in these specific Hamming numbers. But the alternative definition [`1 is in the set, and then so are lots of other things that can be generated from existing known members'] is of a sort that occurs frequently [for example, the set of my relatives consists of me, and then any parent or child of a relative], and generating sets systematically in order is a common problem. So, the solution you should have obtained is quite generic, and generalises to many other situations.
Note that it is important that this set can be generated in order. If doubling, tripling or quintupling ever gave smaller integers, then we would never be sure that generating more of them wouldn't fill in some gaps earlier on, and the only way to be sure of finding the first so-many would be to try all integers in sequence. The Collatz conjecture [`Start with any positive integer; halve it if it is even, otherwise triple it and add 1; keep going, and eventually you will reach 1'; e.g. 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] is difficult to analyse partly because the numbers sometimes get bigger and sometimes smaller.
G12FCO home page.
Next problem class.
Lecture 1.