A345219 -id:A345219 - cp's OEIS frontend

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

Labos Elemer, Jun 17 2002

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

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

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.

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

[#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
```

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

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

Edited by Charles R Greathouse IV, Feb 19 2011

A345220 Number of divisors d of n with an even number of primes not exceeding d.

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 1, 3, 2, 3, 3, 4, 1, 3, 2, 4, 4, 2, 1, 4, 1, 2, 3, 4, 2, 5, 1, 4, 2, 1, 2, 4, 2, 3, 4, 6, 1, 5, 2, 4, 5, 2, 1, 5, 2, 2, 2, 3, 2, 4, 2, 6, 4, 3, 1, 7, 2, 2, 6, 5, 3, 4, 1, 2, 2, 4, 2, 6, 1, 2, 3, 4, 2, 4, 2, 8, 4, 2, 1, 6, 1, 2, 3, 5, 2, 8, 4, 4, 3

Offset: 1

Wesley Ivan Hurt, Jun 11 2021

nonn

Inverse Möbius transform of (pi(n)+1) mod 2 = A131377(n). - Wesley Ivan Hurt, Jul 04 2025

			a(24) = 4; The divisors d of 24 are: 1, 2, 3, 4, 6, 8, 12, 24 and the corresponding values of pi(d) are: 0, 1, 2, 2, 3, 4, 5, 9. There are 4 even values of pi(d).

Cf. A000005 (tau), A000720 (pi), A131377, A345219.

Table[Sum[Mod[PrimePi[d] + 1, 2], {d, Divisors[n]}], {n, 100}]

a(n) = sumdiv(n, d, !(primepi(d) % 2)); \\ Michel Marcus, Jun 11 2021

a(n) = Sum_{d|n} ((pi(d)+1) mod 2).

a(n) = A000005(n) - A345219(n). - Wesley Ivan Hurt, Jul 05 2025

A385625 Sum of the divisors d of n with an odd number of primes not exceeding d.

Original entry on oeis.org

0, 2, 0, 2, 5, 8, 0, 2, 0, 7, 11, 20, 0, 2, 5, 2, 17, 26, 0, 7, 0, 13, 23, 44, 30, 28, 27, 30, 0, 13, 31, 34, 44, 53, 40, 74, 0, 2, 0, 7, 41, 50, 0, 13, 5, 25, 47, 92, 49, 82, 68, 80, 0, 53, 16, 30, 0, 2, 59, 85, 0, 33, 0, 34, 5, 52, 67, 121, 92, 112, 0, 98, 73, 76, 105, 78, 88, 112, 0, 7, 27, 43, 83, 174, 107, 88, 87, 101, 0, 31, 0, 25, 31, 49, 5, 124, 97, 149

Offset: 1

Wesley Ivan Hurt, Jul 05 2025

Inverse Möbius transform of n * (pi(n) mod 2) = n * A071986(n).

			The sum of the divisors d of 12 such that pi(d) is odd gives 2 + 6 + 12 = 20.

Cf. A000203 (sigma), A000720 (pi), A071986, A345219, A385628.

Table[Sum[d*Mod[PrimePi[d], 2], {d, Divisors[n]}], {n, 100}]

a(n) = Sum_{d|n} d * (pi(d) mod 2).

a(n) = A000203(n) - A385628(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A345220 Number of divisors d of n with an even number of primes not exceeding d.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A385625 Sum of the divisors d of n with an odd number of primes not exceeding d.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula