A353283 - OEIS

%I #23 Jun 02 2022 08:31:41

%S 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,

%T 19,15,20,16,23,17,24,18,24,19,27,20,28,21,28,22,31,23,33,24,32,25,36,

%U 26,37,27,36,28,41,29,42,30,40,31,45,32,47,33,44,34,50,35,51,36,48

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

%C Equivalent to removing all multiples of numbers from 2 to smallest divisor of n from the set [2..n].

%C There should be a simple formula.  - _N. J. A. Sloane_, May 29 2022

%H Rémy Sigrist, <a href="/A353283/b353283.txt">Table of n, a(n) for n = 2..10000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>

%F a(2*n) = n - 1 for any n > 0. - _Rémy Sigrist_, Jun 02 2022

%e a(15) = 8 because:

%e First pass: drop multiples of 2:

%e   2 3 x 5 x 7 x 9 x 11 x 13 x 15

%e Second pass: drop multiples of 3:

%e   2 3 _ 5 _ 7 _ x _ 11 _ 13 _ x

%e 15 was dropped so it is not prime; 8 numbers were dropped.

%o (Haskell)

%o f n=n-2-r[2..n] where

%o r(h:t)|n`elem`t=1+r[x|x<- t,x`mod`h>0]

%o        |1>0=length t

%o (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

%Y Cf. A020639, A055396, A055399.

%K nonn

%O 2,5

%A _Nicola Pesenti_, Apr 07 2022