A073311 Number of squarefree numbers in the reduced residue system of n.

1, 1, 2, 2, 3, 2, 5, 4, 4, 3, 7, 4, 8, 5, 6, 7, 11, 6, 12, 7, 8, 9, 15, 8, 13, 10, 13, 9, 17, 8, 19, 13, 13, 13, 15, 11, 23, 15, 17, 14, 26, 11, 28, 17, 18, 18, 30, 15, 26, 17, 21, 19, 32, 16, 25, 20, 23, 23, 36, 15, 37, 25, 26, 26, 30, 18, 41, 26, 29, 22, 44, 22, 45, 30, 29, 29, 36

Offset: 1

Author

Reinhard Zumkeller, Jul 25 2002

Keywords

• nonn

Comments

Number of positive squarefree numbers <= n that are relatively prime to n.

Examples

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; six of them are squarefree: 1, 2, 7, 11, 13 and 14, therefore a(15)=6. [Typo fixed by _Reinhard Zumkeller_, Mar 19 2010]
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Steven R. Finch, Unitarism and infinitarism.
• Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
• Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 49-50.

Crossrefs

Cf. A073312, A005117, A000010, A048864, A048865, A065463.

Programs

Haskell

a073311 = sum . map a008966 . a038566_row
-- Reinhard Zumkeller, Jul 04 2012

Magma

[&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // Marius A. Burtea, Jul 27 2019

Maple

with(numtheory): rad := n -> mul(p, p in factorset(n)):
seq(add(mobius(rad(n)*i)^2, i=1..n), n=1..100); # Ridouane Oudra, Jul 27 2019

Mathematica

a[n_] := Select[Range[n], SquareFreeQ[#] && CoprimeQ[#, n]&] // Length;
Array[a, 100] (* Jean-François Alcover, Dec 12 2021 *)

PARI

a(n)=my(s=1); forfactored(k=2,n-1, if(vecmax(k[2][,2])==1 && gcd(k[1],n)==1, s++)); s \\ Charles R Greathouse IV, Nov 05 2017

Formula

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

Let s(n) = Sum_{k=1..n} a(k). Then s(n) is asymptotic to C*n^2 where C = (3/Pi^2)*alpha and alpha = Product_{p prime} (1 - 1/(p*(p+1))) = A065463 = 0.7044422009... [From discussions in Number Theory List, Apr 06 2004]

A175046(n) = a(n)*A008966(n). - Reinhard Zumkeller, Apr 05 2010

a(n) = Sum_{k=1..A000010(n)} A008966(A038566(n,k)). - Reinhard Zumkeller, Jul 04 2012

a(n) = Sum_{i=1..n} mu(A007947(n)*i)^2, where mu is the Moebius function (A008683). - Ridouane Oudra, Jul 27 2019

a(n) = Sum_{1<=k<=n, gcd(n,k)=1} mu(k)^2. - Ridouane Oudra, May 25 2023