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,5

Links

Table of n, a(n) for n=1..71.

Formula

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

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

Example

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

Mathematica

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

Prog

(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<<len(f:=factorint(n)))+int(max(f.values(), default=1)==1) # Chai Wah Wu, Jan 03 2024

Crossrefs

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

Sequence in context: A296337 A308432 A136692 * A219194 A234306 A223012

Adjacent sequences: A368670 A368671 A368672 * A368674 A368675 A368676

Keyword

nonn,easy

Author

Wesley Ivan Hurt, Jan 02 2024

Status

approved