login
The OEIS is supported by the many generous donors to the OEIS 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)
33
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,6
COMMENTS
Also Moebius transform applied twice to natural numbers.
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
Dirichlet convolution of phi(n) and mu(n). - Richard L. Ollerton, May 07 2021
From Jianing Song, May 21 2022: (Start)
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.
a(n) is the maximum element in the n-th row of A354058 (or A354061). (End)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
H. Jager, On the number of Dirichlet characters with modulus not exceeding x, Nederl. Akad. Wetensch. Proc. Ser. A 76=Indag. Math. 35 (1973) 452-455.
Wolfgang Schramm, The Fourier transform of functions of the greatest common divisor, Electronic Journal of Combinatorial Number Theory A50 (8(1)), 2008.
N. J. A. Sloane, Transforms
FORMULA
Multiplicative with a(p) = p-2 and a(p^e) = (p-1)^2*p^(e-2) for e > 1. - Vladeta Jovovic, Jan 25 2002
Dirichlet g.f.: zeta(s-1)/zeta^2(s).
a(n) = Sum_{k=1..n} mu(gcd(n,k)) for n > 0. - Benoit Cloitre, Jun 14 2007
a(n) = Sum_{k=1..n} (phi(gcd(k,n)) * cos(2*Pi*k/n)). - Enrique Pérez Herrero, Jan 18 2013
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
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
Sum_{k=1..n} a(k) ~ 18 * n^2 / Pi^4. - Vaclav Kotesovec, Nov 04 2018
Sum_{n>=1} a(n)*x^n/(1 - x^n) = Sum_{n>=1} phi(n)*x^n. - Mamuka Jibladze, Aug 09 2019
Sum_{d|n} a(d) = phi(n) (A000010). - Amiram Eldar, Jun 23 2020
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
a(n) = A354058(n,psi(n)) = A354061(n,psi(n)) with psi = A002322. - Jianing Song, May 21 2022
EXAMPLE
From Jianing Song, May 21 2022: (Start)
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.
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)
MAPLE
with(numtheory); f:=n->add( phi(d)*mobius(n/d), d in divisors(n)); [seq(f(n), n=0..120)];
MATHEMATICA
Table[Sum[EulerPhi[d] MoebiusMu[n/d], {d, Divisors[n]}], {n, 0, 86}] (* Jean-François Alcover, Apr 04 2011 *)
Table[DirichletConvolve[MoebiusMu[n], EulerPhi[n], n, m], {m, 86}] (* Jan Mangaldan, Mar 15 2013 *)
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 *)
PROG
(PARI) a(n)=if(n<1, 0, direuler(p=2, n, (1-X)^2/(1-p*X))[n]) \\ Ralf Stephan
(PARI) a(n) = sumdiv(n, d, moebius(d) * eulerphi(n/d) ); \\ Joerg Arndt, Apr 14 2013
(Haskell)
a007431 0 = 0
a007431 n = sum $ map (a008683 . gcd n) [1..n]
-- Reinhard Zumkeller, Jan 06 2014
(Magma) [0] cat [&+[EulerPhi(d)*MoebiusMu(Floor(n/d)):d in Divisors(n)]:n in [1..90]]; // Marius A. Burtea, Aug 10 2019
CROSSREFS
Cf. A007432.
Sequence in context: A236146 A196111 A261628 * A215447 A346692 A159980
KEYWORD
nonn,nice,mult
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)