

A230773


Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.


1



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, 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, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 3, 1, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,9


COMMENTS

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.
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).


LINKS

JeanChristophe Hervé, Table of n, a(n) for n = 1..10000
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
H. B. Meyer, Eratosthenes' sieve
F. Richman, Generating primes by the sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes


FORMULA

a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1A010051(n))*A055396(n)
(that is, if n is prime > 3, a(n) = primepi(firstprimebelow(sqrt(n)); else if n is composite, a(n) = A055396(n)).
a(n) = A055399(n)  A010051(n)*mod(n^2,3).


EXAMPLE

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).
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.
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.


CROSSREFS

Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.
Sequence in context: A160988 A184319 A160987 * A338732 A309026 A160986
Adjacent sequences: A230770 A230771 A230772 * A230774 A230775 A230776


KEYWORD

nonn,easy


AUTHOR

JeanChristophe Hervé, Oct 30 2013


STATUS

approved



