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


 
program HammNumb;
{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON}
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}
{
type
  NativeUInt = longWord;
}
var
  pot   : array[0..2] of NativeUInt;
 
function NextHammNumb(n:NativeUInt):NativeUInt;
var
  q,p,nr : NativeUInt;
begin
  repeat
    nr := n+1;
    n := nr;
 
    p := 0;
    while NOT(ODD(nr)) do
    begin
      inc(p);
      nr := nr div 2;
    end;
    Pot[0]:= p;
 
    p := 0;
    q := nr div 3;
    while q*3=nr do
    Begin
      inc(P);
      nr := q;
      q := nr div 3;
    end;
    Pot[1] := p;
 
    p := 0;
    q := nr div 5;
    while q*5=nr do
    Begin
      inc(P);
      nr := q;
      q := nr div 5;
    end;
    Pot[2] := p;
 
  until nr = 1;
  result:= n;
end;
 
procedure Check;
var
  i,n: NativeUint;
begin
  n := 1;
  for i := 1 to 20 do
  begin
    n := NextHammNumb(n);
    write(n,' ');
  end;
  writeln;
  writeln;
  n := 1;
  for i := 1 to 1690 do
    n := NextHammNumb(n);
  writeln('No ',i:4,' | ',n,' = 2^',Pot[0],' 3^',Pot[1],' 5^',Pot[2]);
end;
 
Begin
  Check;
End.