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


typeset -a hamming=(1)
function nextHamming {
    typeset -Sa q2 q3 q5
    integer h=${hamming[${#hamming[@]}-1]}
    q2+=( $(( h*2 )) )
    q3+=( $(( h*3 )) )
    q5+=( $(( h*5 )) )
    h=$( min3 ${q2[0]} ${q3[0]} ${q5[0]} )
    (( ${q2[0]} == h )) && ashift q2 >/dev/null
    (( ${q3[0]} == h )) && ashift q3 >/dev/null
    (( ${q5[0]} == h )) && ashift q5 >/dev/null
    hamming+=($h)
}
 
function ashift {
    nameref ary=$1
    print -- "${ary[0]}"
    ary=( "${ary[@]:1}" )
}
 
function min3 {
    if (( $1 < $2 )); then
        (( $1 < $3 )) && print -- $1 || print -- $3
    else
        (( $2 < $3 )) && print -- $2 || print -- $3
    fi
}
 
for ((i=1; i<=20; i++)); do
    nextHamming
    printf "%d\t%d\n" $i ${hamming[i-1]}
done
for ((; i<=1690; i++)); do nextHamming; done
nextHamming
printf "%d\t%d\n" $i ${hamming[i-1]}
print "elapsed: $SECONDS"