cp's OEIS Frontend

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

%I A071986 #70 Jul 05 2025 10:23:56
%S A071986 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,
%T A071986 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,
%U A071986 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
%N A071986 Parity of the prime-counting function pi(n).
%C A071986 a(n) + a(n-1) = 1 if and only if n is prime. - _Benoit Cloitre_, Jun 20 2002
%C A071986 Möbius transform of A345219(n). - _Wesley Ivan Hurt_, Jul 05 2025
%H A071986 Henri Lifchitz, <a href="http://www.primenumbers.net/Henri/us/ParPius.htm">Parity of Pi(n)</a>
%H A071986 Terence Tao et al., <a href="http://michaelnielsen.org/polymath1/index.php?title=Prime_counting_function">Prime counting function</a>, Polymath1 project (2009)
%H A071986 Terence Tao, Ernest Croot III, and Harald Helfgott, <a href="https://doi.org/10.1090/S0025-5718-2011-02542-1">Deterministic methods to find primes</a>, Math. Comp. 81 (2012), 1233-1246; <a href="http://arxiv.org/abs/1009.3956">arXiv:1009.3956</a>, [math.NT], 2010-2012.
%F A071986 a(n) = pi(n) mod 2.
%F A071986 a(n) = A000035(A000720(n)). - _Omar E. Pol_, Oct 26 2013
%F A071986 a(n) = Sum_{d|n} A345219(d) * mu(n/d). - _Wesley Ivan Hurt_, Jul 05 2025
%e A071986 a(6)=1 since three primes [2,3,5] are <= 6 and three is odd.
%t A071986 Table[Mod[PrimePi[w], 2], {w, 1, 256}]
%o A071986 (PARI) a(n)=primepi(n)%2
%o A071986 (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;
%o A071986 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
%o A071986 (Magma) [#PrimesUpTo(n) mod 2: n in [1..200]]; // _Vincenzo Librandi_, Jul 21 2019
%Y A071986 Cf. A000035 (n mod 2), A000720 (pi), A008683 (mu), A345219.
%K A071986 nonn,easy
%O A071986 1,1
%A A071986 _Labos Elemer_, Jun 17 2002
%E A071986 Edited by _Charles R Greathouse IV_, Feb 19 2011