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

Comments

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

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.

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 = prod ( 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

Example

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]

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

Prog

(Haskell)
a073311 = sum . map a008966 . a038566_row
-- Reinhard Zumkeller, Jul 04 2012
(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
(Magma) [&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // Marius A. Burtea, Jul 27 2019

Crossrefs

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

Sequence in context: A220949 A029656 A121306 * A347560 A003974 A065769

Adjacent sequences: A073308 A073309 A073310 * A073312 A073313 A073314

Keyword

nonn

Author

Reinhard Zumkeller, Jul 25 2002

Status

approved