login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007431 a(n) = Sum_{d|n} phi(d)*mu(n/d).
(Formerly M2197)
28

%I M2197

%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 Möbius 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

%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^e - 2*p^(e-1) + 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

%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.

%K nonn,nice,mult

%O 0,6

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 14 03:13 EDT 2021. Contains 342941 sequences. (Running on oeis4.)