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