login
A353283
Minimum number of numbers to drop to determine whether n is a prime number using the Sieve of Eratosthenes algorithm.
1
0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 8, 7, 9, 8, 10, 9, 12, 10, 13, 11, 15, 12, 16, 13, 18, 14, 19, 15, 20, 16, 23, 17, 24, 18, 24, 19, 27, 20, 28, 21, 28, 22, 31, 23, 33, 24, 32, 25, 36, 26, 37, 27, 36, 28, 41, 29, 42, 30, 40, 31, 45, 32, 47, 33, 44, 34, 50, 35, 51, 36, 48
OFFSET
2,5
COMMENTS
Equivalent to removing all multiples of numbers from 2 to smallest divisor of n from the set [2..n].
There should be a simple formula. - N. J. A. Sloane, May 29 2022
FORMULA
a(2*n) = n - 1 for any n > 0. - Rémy Sigrist, Jun 02 2022
EXAMPLE
a(15) = 8 because:
First pass: drop multiples of 2:
2 3 x 5 x 7 x 9 x 11 x 13 x 15
Second pass: drop multiples of 3:
2 3 _ 5 _ 7 _ x _ 11 _ 13 _ x
15 was dropped so it is not prime; 8 numbers were dropped.
PROG
(Haskell)
f n=n-2-r[2..n] where
r(h:t)|n`elem`t=1+r[x|x<- t, x`mod`h>0]
|1>0=length t
(PARI) for (n=2, #b=apply (k->if (k==1, 0, primepi(divisors(k)[2])), [1..75]), print1 (sum(k=2, n, b[k]<=b[n])-b[n]", ")) \\ Rémy Sigrist, Jun 02 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Nicola Pesenti, Apr 07 2022
STATUS
approved