/*
Hamming numbers in Picat.
From Rosetta code:
http://rosettacode.org/wiki/Hamming_numbers
"""
Hamming numbers are numbers of the form
H = 2**i * 3**j * 5**k, where i, j, k >= 0.
Hamming numbers are also known as ugly numbers and also 5-smooth numbers
(numbers whose prime divisors are less or equal to 5).
Generate the sequence of Hamming numbers, in increasing order. In particular:
* Show the first twenty Hamming numbers.
* Show the 1691st Hamming number (the last one below 231).
* Show the one millionth Hamming number (if the language – or a
convenient library – supports arbitrary-precision integers).
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
main => go.
go =>
println("using hamming1/1 (map)"),
writeln([hamming(I) : I in 1..20]),
time(writeln(hamming(1691))),
time(writeln(hamming(1000000))), % about 10s
garbage_collect(),
println("using hamming2/1 (array)"),
writeln([hamming2(I) : I in 1..20]),
time(writeln(hamming2(1691))),
time(writeln(hamming2(1000000))), % about 1.5s
nl.
go2 =>
writeln(hamming_life(10)),
nl.
%
% Using map. Slower.
%
hamming(1) = 1.
hamming(2) = 2.
hamming(3) = 3.
hamming(N) = Hamming =>
writeln($hamming(N)),
H = new_map(N),
[Next2, Next3, Next5] = [2,3,5],
H.put(1,1),
H.put(4,0),
H.put(Next2,1),
H.put(Next3,2),
H.put(Next5,3),
I = 0,
J = 0,
K = 0,
M = 1,
while (M < N)
H.put(M, min([Next2,Next3,Next5])),
if H.get(M) == Next2 then I := I+1, Next2 := 2*H.get(I) end,
if H.get(M) == Next3 then J := J+1, Next3 := 3*H.get(J) end,
if H.get(M) == Next5 then K := K+1, Next5 := 5*H.get(K) end,
M := M + 1
end,
HH := H.values(), % adjust for 1-based
Hamming = HH[N-1].
%
% Using arrays.
%
hamming2(1) = 1.
hamming2(2) = 2.
hamming2(3) = 3.
hamming2(N) = Hamming2 =>
writeln($hamming2(N)),
A = new_array(N),
[Next2, Next3, Next5] = [2,3,5],
A[1] := Next2,
A[2] := Next3,
A[3] := Next5,
I = 0,
J = 0,
K = 0,
M = 1,
while (M < N)
A[M] := min([Next2,Next3,Next5]),
if A[M] == Next2 then I := I+1, Next2 := 2*A[I] end,
if A[M] == Next3 then J := J+1, Next3 := 3*A[J] end,
if A[M] == Next5 then K := K+1, Next5 := 5*A[K] end,
M := M + 1
end,
Hamming2 = A[N-1].
% 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36