A368673 Number of squarefree numbers less than n that do not divide n.

0, 0, 1, 1, 2, 1, 4, 4, 4, 3, 6, 4, 7, 6, 7, 9, 10, 8, 11, 9, 10, 11, 14, 12, 14, 13, 15, 13, 16, 11, 18, 18, 17, 18, 19, 19, 22, 21, 22, 22, 25, 20, 27, 25, 25, 26, 29, 27, 29, 27, 28, 28, 31, 29, 30, 30, 31, 32, 35, 29, 36, 35, 35, 37, 36, 33, 40, 38, 39, 36, 43

Offset: 1

Author

Wesley Ivan Hurt, Jan 02 2024

Keywords

• nonn
• easy

Examples

			a(12) = 4 since there are 4 squarefree numbers less than 12 that do not divide 12, namely: 5, 7, 10, and 11.
		

Crossrefs

Cf. A008683 (mu), A064608, A368642, A368674.

Programs

Mathematica

Table[Sum[MoebiusMu[k]^2 (Ceiling[n/k] - Floor[n/k]), {k, n}], {n, 100}]

PARI

a(n) = sum(k=1, n-1, (n % k) && issquarefree(k)); \\ Michel Marcus, Jan 03 2024

Python

from math import isqrt
from sympy import factorint, mobius
def A368673(n): return sum(mobius(k)*((n-1)//k**2) for k in range(1,isqrt(n-1)+1))-(1<Chai Wah Wu, Jan 03 2024

Formula

a(n) = Sum_{k=1..n} mu(k)^2 * (ceiling(n/k) - floor(n/k)).

a(n) = A368642(n) - A064608(n).