What is the set of numbers generated by this sieve called?

167 Views Asked by At

The sieve of Eratosthenes' characterizes the set of prime numbers by sifting composite numbers from the set of natural numbers $> 2$.

Say we use the same sieve to instead sift all perfect powers from the set of natural numbers $>2$.

Does this set of numbers have a name?

The first $25$ numbers generated by the sieve would be: $$ 2,3,5,6,7,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,28,29,30,31,33 $$

E.g., in Haskell I could define Eratosthenes' sieve as follows (where diff is an ordered list difference function, and map maps a function over a list):

multiples n = n : map (\ m -> m + n) (multiples n)
primes (n : ns) = n : diff (primes ns) (multiples n)

The sieve I have in mind is this:

powers n = n : map (\ m -> m * n) (powers n)
nonpowers (n : ns) = n : diff (nonpowers ns) (powers n)
2

There are 2 best solutions below

0
On BEST ANSWER

This sequence is formed by the numbers that are not perfect powers: OEIS/A007916.

1
On

If I understand correctly you're removing the perfect powers. In this case I don't think this particular set has a name.

Also, 24 should be in the remaining list, since it is not a perfect power.