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


import java.math.BigInteger
import java.util.*
 
val Three = BigInteger.valueOf(3)!!
val Five = BigInteger.valueOf(5)!!
 
fun updateFrontier(x : BigInteger, pq : PriorityQueue<BigInteger>) {
    pq.add(x.shiftLeft(1))
    pq.add(x.multiply(Three))
    pq.add(x.multiply(Five))
}
 
fun hamming(n : Int) : BigInteger {
    val frontier = PriorityQueue<BigInteger>()
    updateFrontier(BigInteger.ONE, frontier)
    var lowest = BigInteger.ONE
    for (i in 1 .. n-1) {
        lowest = frontier.poll() ?: lowest
        while (frontier.peek() == lowest)
            frontier.poll()
        updateFrontier(lowest, frontier)
    }
    return lowest
}
 
fun main(args : Array<String>) {
    System.out.print("Hamming(1 .. 20) =")
    for (i in 1 .. 20)
        System.out.print(" ${hamming(i)}")
    System.out.println("\nHamming(1691) = ${hamming(1691)}")
    System.out.println("Hamming(1000000) = ${hamming(1000000)}")
}