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


package main
 
import (
    "fmt"
    "log"
    "math/big"
)
 
var (
    primes      []*big.Int
    smallPrimes []int
)
 
// cache all primes up to 521
func init() {
    two := big.NewInt(2)
    three := big.NewInt(3)
    p521 := big.NewInt(521)
    p29 := big.NewInt(29)
    primes = append(primes, two)
    smallPrimes = append(smallPrimes, 2)
    for i := three; i.Cmp(p521) <= 0; i.Add(i, two) {
        if i.ProbablyPrime(0) {
            primes = append(primes, new(big.Int).Set(i))
            if i.Cmp(p29) <= 0 {
                smallPrimes = append(smallPrimes, int(i.Int64()))
            }
        }
    }
}
 
func min(bs []*big.Int) *big.Int {
    if len(bs) == 0 {
        log.Fatal("slice must have at least one element")
    }
    res := bs[0]
    for _, i := range bs[1:] {
        if i.Cmp(res) < 0 {
            res = i
        }
    }
    return res
}
 
func nSmooth(n, size int) []*big.Int {
    if n < 2 || n > 521 {
        log.Fatal("n must be between 2 and 521")
    }
    if size < 1 {
        log.Fatal("size must be at least 1")
    }
    bn := big.NewInt(int64(n))
    ok := false
    for _, prime := range primes {
        if bn.Cmp(prime) == 0 {
            ok = true
            break
        }
    }
    if !ok {
        log.Fatal("n must be a prime number")
    }
 
    ns := make([]*big.Int, size)
    ns[0] = big.NewInt(1)
    var next []*big.Int
    for i := 0; i < len(primes); i++ {
        if primes[i].Cmp(bn) > 0 {
            break
        }
        next = append(next, new(big.Int).Set(primes[i]))
    }
    indices := make([]int, len(next))
    for m := 1; m < size; m++ {
        ns[m] = new(big.Int).Set(min(next))
        for i := 0; i < len(indices); i++ {
            if ns[m].Cmp(next[i]) == 0 {
                indices[i]++
                next[i].Mul(primes[i], ns[indices[i]])
            }
        }
    }
    return ns
}
 
func main() {
    for _, i := range smallPrimes {
        fmt.Printf("The first 25 %d-smooth numbers are:\n", i)
        fmt.Println(nSmooth(i, 25), "\n")
    }
    for _, i := range smallPrimes[1:] {
        fmt.Printf("The 3,000th to 3,202nd %d-smooth numbers are:\n", i)
        fmt.Println(nSmooth(i, 3002)[2999:], "\n")
    }
    for _, i := range []int{503, 509, 521} {
        fmt.Printf("The 30,000th to 30,019th %d-smooth numbers are:\n", i)
        fmt.Println(nSmooth(i, 30019)[29999:], "\n")
    }
}