%I M2197 #101 May 25 2022 05:58:32
%S 0,1,0,1,1,3,0,5,2,4,0,9,1,11,0,3,4,15,0,17,3,5,0,21,2,16,0,12,5,27,0,
%T 29,8,9,0,15,4,35,0,11,6,39,0,41,9,12,0,45,4,36,0,15,11,51,0,27,10,17,
%U 0,57,3,59,0,20,16,33,0,65,15,21,0,69,8,71,0,16,17,45,0,77,12,36,0,81,5,45,0
%N a(n) = Sum_{d|n} phi(d)*mu(n/d).
%C Also Moebius transform applied twice to natural numbers.
%C Also number of complex primitive Dirichlet characters modulo n and Sum_{k=1..n} a(k) is asymptotic to (18/Pi^4)*n^2. - _Steven Finch_, Feb 16 2006
%C Dirichlet convolution of phi(n) and mu(n). - _Richard L. Ollerton_, May 07 2021
%C From _Jianing Song_, May 21 2022: (Start)
%C a(n) is the number of degree-psi(n) primitive Dirichlet characters mod n, where psi = A002322. Also, a(n) is the number of degree-(k*psi(n)) primitive Dirichlet characters mod n for all k >= 1.
%C a(n) is the maximum element in the n-th row of A354058 (or A354061). (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A007431/b007431.txt">Table of n, a(n) for n = 0..1000</a>
%H H. Jager, <a href="http://dx.doi.org/10.1016/1385-7258(73)90069-3">On the number of Dirichlet characters with modulus not exceeding x</a>, Nederl. Akad. Wetensch. Proc. Ser. A 76=Indag. Math. 35 (1973) 452-455.
%H Wolfgang Schramm, <a href="http://www.emis.de/journals/INTEGERS/papers/i50/i50.Abstract.html">The Fourier transform of functions of the greatest common divisor</a>, Electronic Journal of Combinatorial Number Theory A50 (8(1)), 2008.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F Multiplicative with a(p) = p-2 and a(p^e) = (p-1)^2*p^(e-2) for e > 1. - _Vladeta Jovovic_, Jan 25 2002
%F Dirichlet g.f.: zeta(s-1)/zeta^2(s).
%F a(n) = Sum_{k=1..n} mu(gcd(n,k)) for n > 0. - _Benoit Cloitre_, Jun 14 2007
%F a(n) = Sum_{k=1..n} (phi(gcd(k,n)) * cos(2*Pi*k/n)). - _Enrique Pérez Herrero_, Jan 18 2013
%F a(n) = Sum_{d|n} tau_{-2}(d)*n/d = Sum_{d|n} tau_{-3}(d)*sigma_1(n/d), where tau_{-3} is A007428, tau_{-2} A007427 and sigma_1 A000203. - _Enrique Pérez Herrero_, Jan 19 2013
%F G.f.: Sum_{n>=1} a(n)*x^n/(1 - x^n) = Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2. - _Ilya Gutkovskiy_, Apr 25 2017
%F Sum_{k=1..n} a(k) ~ 18 * n^2 / Pi^4. - _Vaclav Kotesovec_, Nov 04 2018
%F Sum_{n>=1} a(n)*x^n/(1 - x^n) = Sum_{n>=1} phi(n)*x^n. - _Mamuka Jibladze_, Aug 09 2019
%F Sum_{d|n} a(d) = phi(n) (A000010). - _Amiram Eldar_, Jun 23 2020
%F a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - _Richard L. Ollerton_, May 07 2021
%F a(n) = A354058(n,psi(n)) = A354061(n,psi(n)) with psi = A002322. - _Jianing Song_, May 21 2022
%e From _Jianing Song_, May 21 2022: (Start)
%e a(45) = 12: psi(45) = 12, there are 3 degree-12 primitive characters modulo 5 and 4 degree-12 primitive characters modulo 9, so a(45) = 3 * 4 = 12.
%e a(63) = 20: psi(63) = 6, there are 5 sextic primitive characters modulo 7 and 4 sextic primitive characters modulo 9, so a(63) = 5 * 4 = 20. (End)
%p with(numtheory); f:=n->add( phi(d)*mobius(n/d), d in divisors(n)); [seq(f(n),n=0..120)];
%t Table[Sum[EulerPhi[d] MoebiusMu[n/d], {d, Divisors[n]}], {n, 0, 86}] (* _Jean-François Alcover_, Apr 04 2011 *)
%t Table[DirichletConvolve[MoebiusMu[n], EulerPhi[n], n, m], {m, 86}] (* _Jan Mangaldan_, Mar 15 2013 *)
%t f[p_, e_] := If[e == 1, p-2, p^e - 2*p^(e-1) + p^(e-2)]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* _Amiram Eldar_, Jun 23 2020 *)
%o (PARI) a(n)=if(n<1,0,direuler(p=2,n,(1-X)^2/(1-p*X))[n]) \\ _Ralf Stephan_
%o (PARI) a(n) = sumdiv(n,d, moebius(d) * eulerphi(n/d) ); \\ _Joerg Arndt_, Apr 14 2013
%o (Haskell)
%o a007431 0 = 0
%o a007431 n = sum $ map (a008683 . gcd n) [1..n]
%o -- _Reinhard Zumkeller_, Jan 06 2014
%o (Magma) [0] cat [&+[EulerPhi(d)*MoebiusMu(Floor(n/d)):d in Divisors(n)]:n in [1..90]]; // _Marius A. Burtea_, Aug 10 2019
%Y Cf. A007432.
%Y Cf. A000010, A008683, A354058, A354061.
%K nonn,nice,mult
%O 0,6
%A _N. J. A. Sloane_