cp's OEIS Frontend

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

%I A073311 #42 Aug 20 2024 23:17:16
%S A073311 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,
%T A073311 19,13,13,13,15,11,23,15,17,14,26,11,28,17,18,18,30,15,26,17,21,19,32,
%U A073311 16,25,20,23,23,36,15,37,25,26,26,30,18,41,26,29,22,44,22,45,30,29,29,36
%N A073311 Number of squarefree numbers in the reduced residue system of n.
%C A073311 Number of positive squarefree numbers <= n that are relatively prime to n.
%H A073311 Reinhard Zumkeller, <a href="/A073311/b073311.txt">Table of n, a(n) for n = 1..10000</a>
%H A073311 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Unitarism and infinitarism</a>.
%H A073311 Steven R. Finch, <a href="/A007947/a007947.pdf">Unitarism and Infinitarism</a>, February 25, 2004. [Cached copy, with permission of the author]
%H A073311 Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 49-50.
%F A073311 a(n) + A073312(n) = A000010(n).
%F A073311 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]
%F A073311 A175046(n) = a(n)*A008966(n). - _Reinhard Zumkeller_, Apr 05 2010
%F A073311 a(n) = Sum_{k=1..A000010(n)} A008966(A038566(n,k)). - _Reinhard Zumkeller_, Jul 04 2012
%F A073311 a(n) = Sum_{i=1..n} mu(A007947(n)*i)^2, where mu is the Moebius function (A008683). - _Ridouane Oudra_, Jul 27 2019
%F A073311 a(n) = Sum_{1<=k<=n, gcd(n,k)=1} mu(k)^2. - _Ridouane Oudra_, May 25 2023
%e A073311 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]
%p A073311 with(numtheory): rad := n -> mul(p, p in factorset(n)):
%p A073311 seq(add(mobius(rad(n)*i)^2, i=1..n), n=1..100); # _Ridouane Oudra_, Jul 27 2019
%t A073311 a[n_] := Select[Range[n], SquareFreeQ[#] && CoprimeQ[#, n]&] // Length;
%t A073311 Array[a, 100] (* _Jean-François Alcover_, Dec 12 2021 *)
%o A073311 (Haskell)
%o A073311 a073311 = sum . map a008966 . a038566_row
%o A073311 -- _Reinhard Zumkeller_, Jul 04 2012
%o A073311 (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
%o A073311 (Magma) [&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // _Marius A. Burtea_, Jul 27 2019
%Y A073311 Cf. A073312, A005117, A000010, A048864, A048865, A065463.
%K A073311 nonn
%O A073311 1,3
%A A073311 _Reinhard Zumkeller_, Jul 25 2002