OFFSET
1,1
COMMENTS
a(n) + a(n-1) = 1 if and only if n is prime. - Benoit Cloitre, Jun 20 2002
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.
FORMULA
a(n) = pi(n) mod 2.
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
KEYWORD
nonn,easy
AUTHOR
Labos Elemer, Jun 17 2002
EXTENSIONS
Edited by Charles R Greathouse IV, Feb 19 2011
STATUS
approved