cp's OEIS Frontend

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

%I A353283 #23 Jun 02 2022 08:31:41
%S A353283 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 A353283 19,15,20,16,23,17,24,18,24,19,27,20,28,21,28,22,31,23,33,24,32,25,36,
%U A353283 26,37,27,36,28,41,29,42,30,40,31,45,32,47,33,44,34,50,35,51,36,48
%N A353283 Minimum number of numbers to drop to determine whether n is a prime number using the Sieve of Eratosthenes algorithm.
%C A353283 Equivalent to removing all multiples of numbers from 2 to smallest divisor of n from the set [2..n].
%C A353283 There should be a simple formula.  - _N. J. A. Sloane_, May 29 2022
%H A353283 Rémy Sigrist, <a href="/A353283/b353283.txt">Table of n, a(n) for n = 2..10000</a>
%H A353283 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
%F A353283 a(2*n) = n - 1 for any n > 0. - _Rémy Sigrist_, Jun 02 2022
%e A353283 a(15) = 8 because:
%e A353283 First pass: drop multiples of 2:
%e A353283   2 3 x 5 x 7 x 9 x 11 x 13 x 15
%e A353283 Second pass: drop multiples of 3:
%e A353283   2 3 _ 5 _ 7 _ x _ 11 _ 13 _ x
%e A353283 15 was dropped so it is not prime; 8 numbers were dropped.
%o A353283 (Haskell)
%o A353283 f n=n-2-r[2..n] where
%o A353283 r(h:t)|n`elem`t=1+r[x|x<- t,x`mod`h>0]
%o A353283        |1>0=length t
%o A353283 (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 A353283 Cf. A020639, A055396, A055399.
%K A353283 nonn
%O A353283 2,5
%A A353283 _Nicola Pesenti_, Apr 07 2022