|
%I #44 Sep 08 2022 08:45:06
%S 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 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 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 Parity of the prime-counting function pi(n).
%C a(n) + a(n-1) = 1 if and only if n is prime. - _Benoit Cloitre_, Jun 20 2002
%H Henri Lifchitz, <a href="http://www.primenumbers.net/Henri/us/ParPius.htm">Parity of Pi(n)</a>
%H Terence Tao et al., <a href="http://michaelnielsen.org/polymath1/index.php?title=Prime_counting_function">Prime counting function</a>, Polymath1 project (2009)
%H 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 a(n) = pi(n) mod 2.
%F a(n) = A000035(A000720(n)). - _Omar E. Pol_, Oct 26 2013
%e a(6)=1 since three primes [2,3,5] are <= 6 and three is odd.
%t Table[Mod[PrimePi[w], 2], {w, 1, 256}]
%o (PARI) a(n)=primepi(n)%2
%o (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 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 (Magma) [#PrimesUpTo(n) mod 2: n in [1..200]]; // _Vincenzo Librandi_, Jul 21 2019
%Y Cf. A000720.
%K nonn,easy
%O 1,1
%A _Labos Elemer_, Jun 17 2002
%E Edited by _Charles R Greathouse IV_, Feb 19 2011
|
