A071986 Parity of the prime-counting function pi(n).

0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1

Offset

1,1

Comments

a(n) + a(n-1) = 1 if and only if n is prime. - Benoit Cloitre, Jun 20 2002

Links

Table of n, a(n) for n=1..105.

Henri Lifchitz, Parity of Pi(n)

Terence Tao et al., Prime counting function, Polymath1 project (2009)

Terence Tao, Ernest Croot III, and Harald Helfgott, Deterministic methods to find primes, Math. Comp. 81 (2012), 1233-1246; arXiv:1009.3956, [math.NT], 2010-2012.

Formula

a(n) = pi(n) mod 2.

a(n) = A000035(A000720(n)). - Omar E. Pol, Oct 26 2013

Example

a(6)=1 since three primes [2,3,5] are <= 6 and three is odd.

Mathematica

Table[Mod[PrimePi[w], 2], {w, 1, 256}]

Prog

(PARI) a(n)=primepi(n)%2
(PARI) sq(n)=if (n<6, return(max(n-1, 0))); my(s, t); forsquarefree(i=1, sqrtint(n), t=n\i[1]^2; s+=moebius(i)*sum(i=1, sqrtint(t), t\i)); s;
a(n)=my(s); forsquarefree(i=1, logint(n, 2), s+=moebius(i)*sq(sqrtnint(n, i[1]))); s%2 \\ Charles R Greathouse IV, Jan 09 2018
(Magma) [#PrimesUpTo(n) mod 2: n in [1..200]]; // Vincenzo Librandi, Jul 21 2019

Crossrefs

Cf. A000720.

Sequence in context: A104893 A104894 A168393 * A079944 A059652 A108736

Adjacent sequences: A071983 A071984 A071985 * A071987 A071988 A071989

Keyword

nonn,easy

Author

Labos Elemer, Jun 17 2002

Extensions

Edited by Charles R Greathouse IV, Feb 19 2011

Status

approved