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


# Return the index in the input array of the min_by(f) value
def index_min_by(f):
  . as $in
  | if length == 0 then null
    else .[0] as $first
    | reduce range(0; length) as $i 
        ([0, $first, ($first|f)];   # state: [ix; min; f|min]
         ($in[$i]|f) as $v
         | if $v < .[2] then [ $i, $in[$i], $v ] else . end) 
    | .[0]
    end;
 
# Emit n Hamming numbers if n>0; the nth if n<0
def hamming(n):
 
  # input: [twos, threes, fives] of which at least one is assumed to be non-empty
  # output: the index of the array holding the min of the firsts
  def next: map( .[0] ) | index_min_by(.);
 
  # input: [value, [twos, threes, fives] ....]
  # ix is the index in [twos, threes, fives] of the array to be popped
  # output: [popped, updated_arrays ...]
  def pop(ix):
    .[1] as $triple
    | setpath([0];    $triple[ix][0])
    | setpath([1,ix]; $triple[ix][1:]);
 
  # input: [x, [twos, threes, fives], count]
  # push value*2 to twos, value*3 to threes, value*5 to fives and increment count
  def push(v):
    [.[0], [.[1][0] + [2*v], .[1][1] + [3*v], .[1][2] + [5*v]], .[2] + 1];
 
  # _hamming is the workhorse
  # input: [previous, [twos, threes, fives], count]
  def _hamming:
    .[0] as $previous
    | if (n > 0 and .[2] == n) or (n<0 and .[2] == -n) then $previous
      else (.[1]|next) as $ix     # $ix cannot be null
      | pop($ix)
      | .[0] as $next
      | (if $next == $previous then empty elif n>=0 then $previous else empty end), 
        (if $next == $previous then . else push($next) end | _hamming) 
      end;
  [1, [[2],[3],[5]], 1] | _hamming;
 
. as $n | hamming($n)