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

Author

Labos Elemer, Jun 17 2002

Keywords

• nonn
• easy

Comments

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

Möbius transform of A345219(n). - Wesley Ivan Hurt, Jul 05 2025

Examples

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

Links

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

Crossrefs

Cf. A000035 (n mod 2), A000720 (pi), A008683 (mu), A345219.

Programs

Magma

[#PrimesUpTo(n) mod 2: n in [1..200]]; // Vincenzo Librandi, Jul 21 2019

Mathematica

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

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

Formula

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

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

a(n) = Sum_{d|n} A345219(d) * mu(n/d). - Wesley Ivan Hurt, Jul 05 2025

Extensions

Edited by Charles R Greathouse IV, Feb 19 2011