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 nSmoothNumbers(output);
 
const
	primeCount = 538;
	{$ifDef __GPC__} {$setLimit=3889} {$endIf}
	cardinalMax = 3888;
 
type
	cardinal = 0..cardinalMax;
	cardinals = set of cardinal;
	cardinalPositive = 1..cardinalMax;
 
	natural = 1..maxInt;
 
	primeIndex = 1..primeCount;
	list = array[primeIndex] of cardinal;
 
var
	prime: list;
 
{
	\brief performs prime factorization
 
	\param n the number to factorize
	\return list of exponents for a unique integer factorization using primes
 
	This function requires the global `prime` variable to be initialized.
}
function primeFactorization(n: natural): list;
var
	i: primeIndex;
	{
		Instead of writing `[1: 0; 2: 0; 3: 0; …]`, Extended Pascal permits us
		to use an “array completer” for all unspecified values.
	}
	result: list value [otherwise 0];
begin
	for i := 1 to primeCount do
	begin
		while n mod prime[i] = 0 do
		begin
			n := n div prime[i];
			result[i] := result[i] + 1
		end
	end;
 
	{ Nullify result if the utilized `prime` list was insufficient. }
	if n <> 1 then
	begin
		{ `array` literals need an explicit data type specification. }
		result := list[otherwise 0]
	end;
 
	{
		In a Pascal function definition there must be _one_ assignment to the
		(implicitly) declared variable bearing the same name as of the function.
		This will be returned function result.
	}
	primeFactorization := result
end;
 
{
	\brief returns whether a number is an n-smooth number
 
	\param smoothness the maximum permissible prime factor
	\param x the number to check
	\return whether \param x is smoothness-smooth
}
function isSmooth(
		protected smoothness: cardinalPositive;
		protected x: natural
	): Boolean;
	{
		Return set of non-one factors (i.e. non-zero exponent).
 
		Nesting this function permits most compilers to allocate memory
		for variables only if the function is actually needed.
	}
	function factorizationBases: cardinals;
	var
		exponent: list;
		i: primeIndex;
		result: cardinals value [];
	begin
		exponent := primeFactorization(x);
 
		for i := 1 to primeCount do
		begin
			if exponent[i] > 0 then
			begin
				result := result + [prime[i]]
			end
		end;
 
		factorizationBases := result
	end;
begin
	case smoothness of
		1:
		begin
			{
				The value `1` actually does not have a prime factorization, yet as per
				task specification “1 (unity) is always included in n‑smooth numbers.”
			}
			isSmooth := x = 1
		end;
		{ 2‑smooth numbers is an alias for powers of 2 (OEIS sequence A000079) }
		2:
		begin
			isSmooth := 2 pow round(ln(x) / ln(2)) = x
		end
		{ The `otherwise` catch-all-clause is an Extended Pascal extension. }
		otherwise
		begin
			isSmooth := card(factorizationBases - [0..smoothness]) = 0
			{
				`card` (“cardinality”) is an Extended Pascal extension.
				Testing `card(M) = 0` is equivalent to `M = []` (empty set).
			}
		end	
	end
end;
 
{ === ancillary routines =============================================== }
 
{ This is just your regular Eratosthenes prime sieve. }
procedure sieve(var primes: cardinals);
var
	n: natural;
	i: integer;
	multiples: cardinals;
begin
	{ `1` is by definition not a prime number }
	primes := primes - [1];
 
	{ find the next non-crossed number }
	for n := 2 to cardinalMax do
	begin
		if n in primes then
		begin
			multiples := [];
			{ We do _not_ want to remove 1 * n. }
			i := 2 * n;
			while i in [n..cardinalMax] do
			begin
				multiples := multiples + [i];
				i := i + n
			end;
 
			primes := primes - multiples
		end
	end
end;
 
{ This procedure transforms a `set` to an `array`. }
procedure populatePrime;
var
	primes: cardinals value [1..cardinalMax];
	n: natural value 1;
	i: primeIndex value 1;
begin
	sieve(primes);
 
	for i := 1 to primeCount do
	begin
		repeat
		begin
			n := n + 1
		end
		until n in primes;
 
		prime[i] := n
	end
end;
 
{ ### MAIN ############################################################# }
var
	i: primeIndex value primeCount;
	candidate: natural;
	count: cardinal;
begin
	populatePrime;
 
	{ Show the first 25 n-smooth numbers […] }
	{ […] only prime [n] are to be used. }
	while prime[i] > 29 do
	begin
		i := i - 1
	end;
 
	{
		In Pascal, `for` loop limits are evaluated _once_,
		so this is perfectly legal:
	}
	for i := 1 to i do
	begin
		write(prime[i]:4, '-smooth: 1');
 
		count := 1; { `1` already listed. }
		candidate := 2;
 
		while count < 25 do
		begin
			if isSmooth(prime[i], candidate) then
			begin
				write(', ', candidate:1);
				count := count + 1
			end;
			candidate := candidate + 1
		end;
 
		writeLn
	end;
 
	{
		Note, in Pascal, the `for`‑loop iteration variable is not modified.
		At this point in the code, `i` (still) has the value after the `while`-loop.
		[This statement is not true, if a `goto` prematurely exited the `for`‑loop.]
	}
 
	writeLn;
 
	{ […] show three numbers starting with 3,000 […] }
	for i := 2 to i do
	begin
		write(prime[i]:4, '-smooth:');
 
		count := 0;
		candidate := 3000;
 
		while count < 3 do
		begin
			if isSmooth(prime[i], candidate) then
			begin
				write(' ', candidate:1);
				count := count + 1
			end;
			candidate := candidate + 1
		end;
 
		writeLn
	end;
end.