A073312 Number of nonsquarefree numbers in the reduced residue system of n.

0, 0, 0, 0, 1, 0, 1, 0, 2, 1, 3, 0, 4, 1, 2, 1, 5, 0, 6, 1, 4, 1, 7, 0, 7, 2, 5, 3, 11, 0, 11, 3, 7, 3, 9, 1, 13, 3, 7, 2, 14, 1, 14, 3, 6, 4, 16, 1, 16, 3, 11, 5, 20, 2, 15, 4, 13, 5, 22, 1, 23, 5, 10, 6, 18, 2, 25, 6, 15, 2, 26, 2, 27, 6, 11, 7, 24, 2, 29, 4, 17, 8, 31, 1, 23, 8, 17, 8, 33, 1, 28

Offset

1,9

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Formula

a(n) + A073311(n) = A000010(n).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (3/Pi^2) * (1 - A065463) = 0.0898387... . - Amiram Eldar, Dec 07 2023

Example

n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; two of them are not squarefree: 4 and 8, therefore a(15)=2.

Mathematica

a[n_] := EulerPhi[n] - Module[{rad = Times @@ (First@# & /@ FactorInteger[n])}, Sum[MoebiusMu[k*rad]^2, {k, 1, n}]]; Array[a, 100] (* Amiram Eldar, Mar 08 2020 *)

Crossrefs

Cf. A073311, A013929, A000010, A048864, A048865.

Cf. A065463, A104141.

Sequence in context: A262677 A307742 A297109 * A350941 A166514 A246024

Adjacent sequences: A073309 A073310 A073311 * A073313 A073314 A073315

Keyword

nonn

Author

Reinhard Zumkeller, Jul 25 2002

Status

approved