Hamming numbers are numbers of the form  

    H = 2i × 3j × 5k
           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).



Task

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).


Related tasks

 Humble numbers
 N-smooth numbers


References

 Wikipedia entry:   Hamming numbers     (this link is re-directed to   Regular number).
 Wikipedia entry:   Smooth number
 OEIS entry:   A051037   5-smooth   or   Hamming numbers
 Hamming problem from Dr. Dobb's CodeTalk (dead link as of Sep 2011; parts of the thread here and here).


with javascript_semantics 
function hamming(integer N)
sequence h = repeat(1,N)
atom x2 = 2, x3 = 3, x5 = 5, hn
integer i = 1, j = 1, k = 1
    for n=2 to N do
        hn = min(x2,min(x3,x5))
        h[n] = hn
        if hn==x2 then i += 1 x2 = 2*h[i] end if
        if hn==x3 then j += 1 x3 = 3*h[j] end if
        if hn==x5 then k += 1 x5 = 5*h[k] end if
    end for
    return h[N]
end function
 
include builtins\mpfr.e
 
function mpz_hamming(integer N)
sequence h = mpz_inits(N,1)
mpz x2 = mpz_init(2),
    x3 = mpz_init(3),
    x5 = mpz_init(5),
    hn = mpz_init()
integer i = 1, j = 1, k = 1
    for n=2 to N do
        mpz_set(hn,mpz_min({x2,x3,x5}))
        mpz_set(h[n],hn)
        if mpz_cmp(hn,x2)=0 then i += 1 mpz_mul_si(x2,h[i],2) end if
        if mpz_cmp(hn,x3)=0 then j += 1 mpz_mul_si(x3,h[j],3) end if
        if mpz_cmp(hn,x5)=0 then k += 1 mpz_mul_si(x5,h[k],5) end if
    end for
    return h[N]
end function
 
sequence s = {}
for i=1 to 20 do
    s = append(s,hamming(i))
end for
?s
printf(1,"%d\n",hamming(1691))
printf(1,"%d (wrong!)\n",hamming(1000000)) --(the hn==x2 etc fail, so multiplies are all wrong)
 
printf(1,"%s\n",{mpz_get_str(mpz_hamming(1691))})
printf(1,"%s\n",{mpz_get_str(mpz_hamming(1000000))})
