|
%I #63 Apr 03 2023 10:36:13
%S 0,0,1,1,1,1,1,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,3,1,2,1,3,1,3,1,2,1,
%T 3,1,3,1,2,1,3,1,3,1,2,1,3,1,4,1,2,1,4,1,3,1,2,1,4,1,4,1,2,1,3,1,4,1,
%U 2,1,4,1,4,1,2,1,4,1,4,1,2,1,4,1,3,1,2
%N Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.
%C This sequence differs from A055399 on prime numbers; as they are never removed during the sieve, it is partly a matter of convention to decide at which step they are classified as prime. Because the smallest integer to be removed at step k is prime(k)^2, integers between prime(k)^2 and prime(k+1)^2 and not removed after step k are known as prime after this step.
%C This is how this sequence is defined for noncomposite numbers (primes and 1): for any noncomposite number n between prime(k)^2 and prime(k+1)^2, a(n) = k. An exception is made for 3 to fit the usual presentation of the sieve, according to which 3 is classified as prime after the first step, that is, a(3) = 1 (it can be argued, though, that running the first step of the sieve is not actually necessary to identify 3 as prime because 3 < prime(1)^2: see the comment on A000040 by Daniel Forgues, referring to 2 and 3 as "forcibly prime" since there are no integers greater than 1 and less than or equal to their respective square roots).
%H Jean-Christophe Hervé, <a href="/A230773/b230773.txt">Table of n, a(n) for n = 1..10000</a>
%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php/SieveOfEratosthenes.html">Sieve of Eratosthenes</a>
%H H. B. Meyer, <a href="http://www.hbmeyer.de/eratosiv.htm">Eratosthenes' sieve</a>
%H F. Richman, <a href="http://math.fau.edu/Richman/primes.htm">Generating primes by the sieve of Eratosthenes</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
%F a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1-A010051(n))*A055396(n)
%F (that is, if n is prime > 3, a(n) = primepi(firstprimebelow(sqrt(n)); else if n is composite, a(n) = A055396(n)).
%F a(n) = A055399(n) - A010051(n)*mod(n^2,3).
%e By convention, a(1)=a(2)=0, as 1 is not involved in the sieve, and 2 is known as prime before the first step (first integer > 1).
%e At step 1, multiples of 2 are removed, beginning with 4 = 2*2; 5 and 7 are not removed and cannot be removed at any further step because they are less than 3*3 = 9; therefore, integers from 4 to 8 are all classified as prime or not prime after the first step: a(4) = a(5) = a(6) = a(7) = a(8) = 1.
%e At step 2, all integers < 5^2 = 25 will be classified because those >= 9 and not already classified at step one are either multiple of 3 or prime; therefore, for 9 <= n < 25, a(n) = 1 if n is even, a(n) = 2 if n is odd.
%Y Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.
%K nonn,easy
%O 1,9
%A _Jean-Christophe Hervé_, Oct 30 2013
|
