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

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

Author

Wesley Ivan Hurt, Jun 11 2021

Keywords

• nonn

Comments

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

Examples

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

Crossrefs

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

Programs

Mathematica

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

PARI

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

Formula

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

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