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

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

Offset: 1

Author

Jean-Christophe Hervé, Oct 30 2013

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

• Jean-Christophe 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

Crossrefs

Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.

Formula

a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1-A010051(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).