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


require "big"
 
def prime?(n) # P3 Prime Generator primality test
  return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5
  sqrt_n = Math.isqrt(n)  # For Crystal < 1.2.0 use Math.sqrt(n).to_i
  pc = typeof(n).new(5)
  while pc <= sqrt_n
    return false if n % pc == 0 || n % (pc + 2) == 0
    pc += 6
  end
  true
end
 
def gen_primes(a, b)
    (a..b).select { |pc| pc if prime? pc }
end
 
def nsmooth(n, limit)
    raise "Exception(n or limit)" if n < 2 || n > 521 || limit < 1
    raise "Exception(must be a prime number: n)" unless prime? n
 
    primes = gen_primes(2, n)
    ns = [0.to_big_i] * limit
    ns[0] = 1.to_big_i
    nextp = primes[0..primes.index(n)].map { |prm| prm.to_big_i }
 
    indices = [0] * nextp.size
    (1...limit).each do |m|
        ns[m] = nextp.min
        (0...indices.size).each do |i|
            if ns[m] == nextp[i]
                indices[i] += 1
                nextp[i] = primes[i] * ns[indices[i]]
            end
        end
    end
    ns
end
 
gen_primes(2, 29).each do |prime|
    print "The first 25 #{prime}-smooth numbers are: \n"
    print nsmooth(prime, 25)
    puts
end
puts
gen_primes(3, 29).each do |prime|
    print "The 3000 to 3202 #{prime}-smooth numbers are: "
    print nsmooth(prime, 3002)[2999..]
    puts
end
puts
gen_primes(503, 521).each do |prime|
    print "The 30,000 to 30,019 #{prime}-smooth numbers are: \n"
    print nsmooth(prime, 30019)[29999..]
    puts
end