Dijkstra attributes to Hamming the problem of building the infinite ascending sequence of all positive numbers greater than 1 containing no prime factors other than 2, 3 and 5, i.e. numbers of the form 2^i x 3^j x 5^k (i,j,k >= 0). The ideas to compute them are the following:
- Given a hamming number h, then 2h, 3h, 5h are hamming numbers.
- 1 is a hamming number at it is used to start the computation.
- To maintain them sorted, it is only needed to compare the numbers coming from the multiplication for 2, 3, 5 not used yet. Other products will result greater than some of then, so they are not candidates to be the first in the sorted list.
The solution is more complicated. We need queues to simulate lazy evaluation. In fact, we need a queue for the numbers that have been multiplied by 2, 3, and 5. The number 1 is inserted in all the queues to start the computation. Difference lists can be used to easily implement queues. The lazy behaviour is got by using multiple answers.
generate (dif(Twos,[V2|L2]), dif(Threes,[V3|L3]), dif(Fives,[V5|L5]))
:- select (Twos, Threes, Fives, V),
dequeue (Twos, Twos1, V),
dequeue (Threes, Threes1, V),
dequeue (Fives, Fives1, V),
V2 is 2*V, V3 is 3*V, V5 is 5*V, write (V), nl,
generate (dif (Twos1, L2), dif (Threes1, L3), dif (Fives1, L5)).
select ([X1|L1], [X2|L2], [X3|L3], X1) :- X1 =< X2, X1 =< X3.
select ([X1|L1], [X2|L2], [X3|L3], X2) :- X2 < X1, X2 =< X3.
select ([X1|L1], [X2|L2], [X3|L3], X3) :- X3 < X1, X3 < X2.
dequeue ([X|L], L, X].
dequeue ([Y|L], [Y|L], X) :- X = Y.
hamming :- generate (dif([1|L2], L2), dif([1|L3], L3), dif([1|L5], L5)).
See also the Functional solution.
Go to index