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


use strict;
use warnings;
use feature 'say';
use ntheory qw<primes>;
use List::Util qw<min>;
 
#use bigint     # works, but slow
use Math::GMPz; # this module gives roughly 16x speed-up
 
sub smooth_numbers {
#    my(@m) = @_;                               # use with 'bigint'
    my @m = map { Math::GMPz->new($_) } @_;     # comment out to NOT use Math::GMPz
    my @s;
    push @s, [1] for 0..$#m;
 
    return sub {
    my $n = $s[0][0];
    $n = min $n, $s[$_][0] for 1..$#m;
    for (0..$#m) {
            shift @{$s[$_]} if $s[$_][0] == $n;
            push @{$s[$_]}, $n * $m[$_]
        }
        return $n
    }
}
 
sub abbrev {
    my($n) = @_;
    return $n if length($n) <= 50;
    substr($n,0,10) . "...(@{[length($n) - 2*10]} digits omitted)..." . substr($n, -10, 10)
}
 
my @primes = @{primes(10_000)};
 
my $start = 3000; my $cnt = 3;
for my $n_smooth (0..9) {
    say "\nFirst 25, and ${start}th through @{[$start+2]}nd $primes[$n_smooth]-smooth numbers:";
    my $s = smooth_numbers(@primes[0..$n_smooth]);
    my @S25;
    push @S25, $s->() for 1..25;
    say join ' ', @S25;
 
    my @Sm; my $c = 25;
    do {
        my $sn = $s->();
        push @Sm, abbrev($sn) if ++$c >= $start;
    } until @Sm == $cnt;
    say join ' ', @Sm;
}
 
$start = 30000; $cnt = 20;
for my $n_smooth (95..97) { # (503, 509, 521) {
    say "\n${start}th through @{[$start+$cnt-1]}th $primes[$n_smooth]-smooth numbers:";
    my $s = smooth_numbers(@primes[0..$n_smooth]);
    my(@Sm,$c);
    do {
        my $sn = $s->();
        push @Sm, $sn if ++$c >= $start;
    } until @Sm == $cnt;
    say join ' ', @Sm;
}