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 Data.Numbers.Primes (primes)
import Text.Printf (printf)
 
 
merge :: Ord a => [a] -> [a] -> [a]
merge [] b = b
merge a@(x:xs) b@(y:ys) | x < y     = x : merge xs b
                        | otherwise = y : merge a ys
 
nSmooth :: Integer -> [Integer]
nSmooth p = 1 : foldr u [] factors
 where
   factors = takeWhile (<=p) primes
   u n s = r
    where r = merge s (map (n*) (1:r))
 
main :: IO ()
main = do
  mapM_ (printf "First 25 %d-smooth:\n%s\n\n" <*> showTwentyFive) firstTenPrimes
  mapM_
    (printf "The 3,000 to 3,202 %d-smooth numbers are:\n%s\n\n" <*> showRange1)
    firstTenPrimes
  mapM_
    (printf "The 30,000 to 30,019 %d-smooth numbers are:\n%s\n\n" <*> showRange2)
    [503, 509, 521]
  where
    firstTenPrimes = take 10 primes
    showTwentyFive = show . take 25 . nSmooth
    showRange1 = show . ((<$> [2999 .. 3001]) . (!!) . nSmooth)
    showRange2 = show . ((<$> [29999 .. 30018]) . (!!) . nSmooth)