% Finds the first N positive integers having no prime factors other than % 2, 3 and 5. These integers are called Hamming numbers or 5-smooth numbers. % e.g. hamming(26, Xs) gives % Xs=[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] hamming(N, [1|Xs]):- init_queue(2, Q), init_queue(3, R), init_queue(5, S), hamming_1(N, Q, R, S, Xs). hamming_1(1, _, _, _, []):-!. hamming_1(I, Q, R, S, [X|Xs]):- I > 1, peek(Q, A), peek(R, B), peek(S, C), min([A,B,C], X), % The smallest of the values at the front of the queues update(Q, X, Q1), update(R, X, R1), update(S, X, S1), I1 is I - 1, hamming_1(I1, Q1, R1, S1, Xs). % Returns the smallest number in the list. min([X|Xs], Y):-min_1(Xs, X, Y). min_1([], X, X). min_1([Y|Ys], X, Z):-Y =< X, !, min_1(Ys, Y, Z). min_1([_|Ys], X, Z):-min_1(Ys, X, Z). % Updates the queues. update(Q, X, Q1):- dequeue(X, Q, Q2), !, % X was at the front of this queue; it has been removed id(Q, P), % P is the prime number associated with this queue Y is X * P, enqueue(Y, Q2, Q1). % X*P has been put at the end of the queue update(Q, X, Q1):- % X is not at the front of this queue id(Q, P), % P is the prime number associated with this queue Y is X * P, enqueue(Y, Q, Q1). % X*P has been put at the end of the queue % Initializes a queue. init_queue(P, q(P,[P|Zs],Zs)). % Adds an element to the end of the queue. enqueue(X, q(P,Ys,[X|Zs]), q(P,Ys,Zs)). % Removes an element from the front of the queue. dequeue(X, q(P,[X|Ys],Zs), q(P,Ys,Zs)). % Returns the value of the element at the front of the queue. peek(q(_,[X|_],_), X). % Returns the prime number, multiples of which are contained in the queue. id(q(P,_,_), P).