A353283 Minimum number of numbers to drop to determine whether n is a prime number using the Sieve of Eratosthenes algorithm.

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

Links

Rémy Sigrist, Table of n, a(n) for n = 2..10000

Wikipedia, Sieve of Eratosthenes

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

Cf. A020639, A055396, A055399.

Sequence in context: A263574 A366701 A278496 * A163464 A317137 A139327

Adjacent sequences: A353280 A353281 A353282 * A353284 A353285 A353286

Keyword

nonn

Author

Nicola Pesenti, Apr 07 2022

Status

approved