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


# Lazily generate the three Hamming numbers that can be derived directly
#   from a known Hamming number h
class Triplet : Class (cv, ce)
 
    method nextVal()
        suspend cv := @ce
    end
 
    initially (baseNum)
        cv := 2*baseNum
        ce := create (3|5)*baseNum
end
 
# Generate Hamming numbers, in order.  Default is first 30
#  But an optional argument can be used to generate more (or less)
#   e.g. hamming 5000 generates the first 5000.
procedure main(args)
    limit := integer(args[1]) | 30
    every write("\t", generateHamming() \ limit)
end
 
# Do the work.   Start with known Hamming number 1 and maintain
#   a set of triplet Hamming numbers as they get derived from that
#   one.  Most of the code here is to figure out which Hamming
#   number is next in sequence (while removing duplicates)
procedure generateHamming()
    triplers := set()
    insert(triplers, Triplet(1))
 
    suspend 1
    repeat {
        # Pick a Hamming triplet that *may* have the next smallest number
        t1 := !triplers         # any will do to start
 
        every t1 ~=== (t2 := !triplers) do {
            if t1.cv > t2.cv then {
               # oops we were wrong, switch assumption
               t1 := t2
               }
            else if t1.cv = t2.cv then {
               # t2's value is a duplicate, so
               # advance triplet t2, if none left in t2, remove it
               t2.nextVal() | delete(triplers, t2)
               }
           }
 
        # Ok, t1 has the next Hamming number, grab it
        suspend t1.cv
        insert(triplers, Triplet(t1.cv)) 
        # Advance triplet t1, if none left in t1, remove it
        t1.nextVal() | delete(triplers, t1)
        }
end