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


class Hamming {
 
    static final ONE = BigInteger.ONE
    static final THREE = BigInteger.valueOf(3)
    static final FIVE = BigInteger.valueOf(5)
 
    static void main(args) {
        print 'Hamming(1 .. 20) ='
        (1..20).each {
            print " ${hamming it}"
        }
        println "\nHamming(1691) = ${hamming 1691}"
        println "Hamming(1000000) = ${hamming 1000000}"
    }
 
    static hamming(n) {
        def priorityQueue = new PriorityQueue<BigInteger>()
        priorityQueue.add ONE
 
        def lowest
 
        n.times {
            lowest = priorityQueue.poll()
            while (priorityQueue.peek() == lowest) {
                priorityQueue.poll()
            }
            updateQueue(priorityQueue, lowest)
        }
 
        lowest
    }
 
    static updateQueue(priorityQueue, lowest) {
        priorityQueue.add(lowest.shiftLeft 1)
        priorityQueue.add(lowest.multiply THREE)
        priorityQueue.add(lowest.multiply FIVE)
    }
}