n-smooth   numbers are positive integers which have no prime factors  >  n.

The   n   (when using it in the expression)   n-smooth   is always prime,

there are   no   9-smooth numbers.

1   (unity)   is always included in n-smooth numbers.




2-smooth   numbers are non-negative powers of two.

5-smooth   numbers are also called   Hamming numbers.

7-smooth   numbers are also called    humble   numbers.



A way to express   11-smooth   numbers is:

  11-smooth  =  2i × 3j × 5k × 7m × 11p

           where     i, j, k, m, p ≥ 0  



Task

   calculate and show the first   25   n-smooth numbers   for   n=2   ───►   n=29
   calculate and show   three numbers starting with   3,000   n-smooth numbers   for   n=3   ───►   n=29
   calculate and show twenty numbers starting with  30,000   n-smooth numbers   for   n=503   ───►   n=521   (optional)


All ranges   (for   n)   are to be inclusive, and only prime numbers are to be used.

The (optional) n-smooth numbers for the third range are:   503,   509,   and   521.

Show all n-smooth numbers for any particular   n   in a horizontal list.

Show all output here on this page.



Related tasks

   Hamming numbers
   humble numbers


References

   Wikipedia entry:   Hamming numbers     (this link is re-directed to   Regular number).
   Wikipedia entry:   Smooth number
   OEIS entry:   A000079    2-smooth numbers or non-negative powers of two
   OEIS entry:   A003586    3-smooth numbers
   OEIS entry:   A051037    5-smooth numbers or Hamming numbers
   OEIS entry:   A002473    7-smooth numbers or humble numbers
   OEIS entry:   A051038   11-smooth numbers
   OEIS entry:   A080197   13-smooth numbers
   OEIS entry:   A080681   17-smooth numbers
   OEIS entry:   A080682   19-smooth numbers
   OEIS entry:   A080683   23-smooth numbers


 
program N_smooth_numbers;
 
{$APPTYPE CONSOLE}
{$R *.res}
 
uses
  System.SysUtils,
  System.Generics.Collections,
  Velthuis.BigIntegers;
 
var
  primes: TList<BigInteger>;
  smallPrimes: TList<Integer>;
 
function IsPrime(value: BigInteger): Boolean;
var
  v: BigInteger;
begin
  if value < 2 then
    exit(False);
 
  for v in [2, 3, 5, 7, 11, 13, 17, 19, 23] do
  begin
    if (value mod v) = 0 then
      exit(value = v);
  end;
 
  v := 29;
 
  while v * v < value do
  begin
    if (value mod v) = 0 then
      exit(False);
    inc(value, 2);
    if (value mod v) = 0 then
      exit(False);
    inc(v, 4);
  end;
 
  Result := True;
end;
 
function Min(values: TList<BigInteger>): BigInteger;
var
  value: BigInteger;
begin
  if values.Count = 0 then
    exit(0);
 
  Result := values[0];
  for value in values do
  begin
    if value < Result then
      result := value;
  end;
end;
 
function NSmooth(n, size: Integer): TList<BigInteger>;
var
  bn, p: BigInteger;
  ok: Boolean;
  i: Integer;
  next: TList<BigInteger>;
  indices: TList<Integer>;
  m: Integer;
begin
  Result := TList<BigInteger>.Create;
  if (n < 2) or (n > 521) then
    raise Exception.Create('Argument out of range: "n"');
 
  if (size < 1) then
    raise Exception.Create('Argument out of range: "size"');
 
  bn := n;
  ok := false;
  for p in primes do
  begin
    ok := bn = p;
    if ok then
      break;
  end;
 
  if not ok then
    raise Exception.Create('"n" must be a prime number');
 
  Result.Add(1);
 
  for i := 1 to size - 1 do
    Result.Add(0);
 
  next := TList<BigInteger>.Create;
 
  for p in primes do
  begin
    if p > bn then
      Break;
    next.Add(p);
  end;
 
  indices := TList<Integer>.Create;
  for i := 0 to next.Count - 1 do
    indices.Add(0);
 
  for m := 1 to size - 1 do
  begin
    Result[m] := Min(next);
    for i := 0 to indices.Count - 1 do
      if Result[m] = next[i] then
      begin
        indices[i] := indices[i] + 1;
        next[i] := primes[i] * Result[indices[i]];
      end;
  end;
 
  indices.Free;
  next.Free;
end;
 
procedure Init();
var
  i: BigInteger;
begin
  primes := TList<BigInteger>.Create;
  smallPrimes := TList<Integer>.Create;
  primes.Add(2);
  smallPrimes.Add(2);
 
  i := 3;
  while i <= 521 do
  begin
    if IsPrime(i) then
    begin
 
      primes.Add(i);
      if i <= 29 then
        smallPrimes.Add(Integer(i));
    end;
    inc(i, 2);
  end;
 
end;
 
procedure Println(values: TList<BigInteger>; CanFree: Boolean = False);
var
  value: BigInteger;
begin
  Write('[');
  for value in values do
    Write(value.ToString, ', ');
  Writeln(']'#10);
 
  if CanFree then
    values.Free;
end;
 
procedure Finish();
begin
  primes.Free;
  smallPrimes.Free;
end;
 
var
  p: Integer;
  ns: TList<BigInteger>;
 
const
  RANGE_3: array[0..2] of integer = (503, 509, 521);
 
begin
  Init;
  for p in smallPrimes do
  begin
    Writeln('The first ', p, '-smooth numbers are:');
    Println(NSmooth(p, 25), True);
  end;
 
  smallPrimes.Delete(0);
  for p in smallPrimes do
  begin
    Writeln('The 3,000 to 3,202 ', p, '-smooth numbers are:');
    ns := nSmooth(p, 3002);
    ns.DeleteRange(0, 2999);
    println(ns, True);
  end;
 
  for p in RANGE_3 do
  begin
    Writeln('The 3,000 to 3,019 ', p, '-smooth numbers are:');
    ns := nSmooth(p, 30019);
    ns.DeleteRange(0, 29999);
    println(ns, True);
  end;
 
  Finish;
  Readln;
end.
 