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


import BigInt
import Foundation
 
extension BinaryInteger {
  @inlinable
  public var isPrime: Bool {
    if self == 0 || self == 1 {
      return false
    } else if self == 2 {
      return true
    }
 
    let max = Self(ceil((Double(self).squareRoot())))
 
    for i in stride(from: 2, through: max, by: 1) {
      if self % i == 0 {
        return false
      }
    }
 
    return true
  }
}
 
@inlinable
public func smoothN<T: BinaryInteger>(n: T, count: Int) -> [T] {
  let primes = stride(from: 2, to: n + 1, by: 1).filter({ $0.isPrime })
  var next = primes
  var indices = [Int](repeating: 0, count: primes.count)
  var res = [T](repeating: 0, count: count)
 
  res[0] = 1
 
  guard count > 1 else {
    return res
  }
 
  for m in 1..<count {
    res[m] = next.min()!
 
    for i in 0..<indices.count where res[m] == next[i] {
      indices[i] += 1
      next[i] = primes[i] * res[indices[i]]
    }
  }
 
  return res
}
 
for n in 2...29 where n.isPrime {
  print("The first 25 \(n)-smooth numbers are: \(smoothN(n: n, count: 25))")
}
 
print()
 
for n in 3...29 where n.isPrime {
  print("The 3000...3002 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 3002).dropFirst(2999).prefix(3))")
}
 
print()
 
for n in 503...521 where n.isPrime {
  print("The 30,000...30,019 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 30_019).dropFirst(29999).prefix(20))")
}