A130054 -id:A130054 - cp's OEIS frontend

A007431 a(n) = Sum_{d|n} phi(d)*mu(n/d).

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

Offset: 0

N. J. A. Sloane

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)

			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)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antti Karttunen, Table of n, a(n) for n = 0..20000 (terms 0..1000 from T. D. Noe)
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

Cf. A007432.

Cf. A000010, A008683, A130054 (Dirichlet inverse), A354058, A354061.

a007431 0 = 0
a007431 n = sum $ map (a008683 . gcd n) [1..n]
-- Reinhard Zumkeller, Jan 06 2014

[0] cat [&+[EulerPhi(d)*MoebiusMu(Floor(n/d)):d in Divisors(n)]:n in [1..90]]; // Marius A. Burtea, Aug 10 2019

with(numtheory); f:=n->add( phi(d)*mobius(n/d), d in divisors(n)); [seq(f(n),n=0..120)];

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 *)

a(n)=if(n<1,0,direuler(p=2,n,(1-X)^2/(1-p*X))[n]) \\ Ralf Stephan

a(n) = sumdiv(n,d, moebius(d) * eulerphi(n/d) ); \\ Joerg Arndt, Apr 14 2013

A007431(n) = if(!n,n,my(f=factor(n)); prod(i=1, #f~, if(1==f[i, 2], f[i, 1]-2, ((f[i,1]-1)^2)*(f[i, 1]^(f[i, 2]-2))))); \\ Antti Karttunen, Dec 15 2024, after Vladeta Jovovic's multiplicative 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

A129691 Inverse of A054523.

Original entry on oeis.org

1, -1, 1, -2, 0, 1, -1, -1, 0, 1, -4, 0, 0, 0, 1, 2, -2, -1, 0, 0, 1, -6, 0, 0, 0, 0, 0, 1, -1, -1, 0, -1, 0, 0, 0, 1, -2, 0, -2, 0, 0, 0, 0, 0, 1, 4, -4, 0, 0, -1, 0, 0, 0, 0, 1, -10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, -1, -2, 0, -1, 0, 0, 0, 0, 0, 1

Offset: 1

Gary W. Adamson, May 04 2007

Row sums = A130054, (1, -1, -1, -3, 0, -5, -2, -3, 0, ...). A129691 * A126988 = A051731. Left column = A023900: (1, -1, -2, -1, -4, 2, -6, ...).

			First few rows of the triangle:
   1;
  -1,  1;
  -2,  0,  1;
  -1, -1,  0,  1;
  -4,  0,  0,  0,  1;
   2, -2, -1,  0,  0,  1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Cf. A054523, A130055, A023900, A126988, A051731.

T(n,k)={if(n%k, 0, sumdivmult(n/k, d, d*moebius(d)))} \\ Andrew Howroyd, Aug 03 2018

A054523^(-1), as an infinite lower triangular matrix.

T(n,k) = A023900(n/k) for k | n, T(n,k) = 0 otherwise. - Andrew Howroyd, Aug 03 2018

Terms a(56) and beyond from Andrew Howroyd, Aug 03 2018

A006580 a(n) = Sum_{k=1..n-1} lcm(k,n-k).

Original entry on oeis.org

0, 0, 1, 4, 8, 20, 21, 56, 60, 96, 105, 220, 152, 364, 301, 360, 464, 816, 549, 1140, 760, 1036, 1221, 2024, 1196, 2200, 2041, 2484, 2184, 4060, 2205, 4960, 3664, 4224, 4641, 5180, 4008, 8436, 6517, 7072, 5980, 11480, 6321, 13244, 8888, 9540, 11661, 17296

Offset: 0

N. J. A. Sloane

nonn

Marc LeBrun, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1000 terms from Reinhard Zumkeller)
Marc Le Brun, Email to N. J. A. Sloane, Jul 1991.

Antidiagonal sums of array A003990.
Cf. A209295.
Cf. A000010, A023900, A057660, A130054.

a006580 n = a006580_list !! (n-1)
a006580_list = map sum a003990_tabl
-- Reinhard Zumkeller, Aug 05 2012

a:= n-> add(ilcm(j, n-j), j=0..n):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 25 2019

Table[ Sum[ LCM[ k, n-k ], {k, 1, n-1} ], {n, 2, 50} ] (* Olivier Gérard, Aug 15 1997 *)
f1[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); f2[p_, e_] := 1 - (p - 1)*e; a[n_] := (Times @@ f1 @@@ (fct = FactorInteger[n]) - Times @@ f2 @@@ fct)*n/6; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Apr 28 2023 *)

a(n) = sum(k=1, n-1, lcm(k, n-k)); \\ Michel Marcus, Aug 11 2017

For n > 0, a(n) = (n/6)*Sum_{d|n} (d*phi(d) - A023900(d)). - Sebastian Karlsson, Oct 02 2021

a(n) = (n/6) * (A057660(n) - A130054(n)), for n > 0. - Amiram Eldar, Apr 28 2023

More terms from Olivier Gérard, Aug 15 1997

A323912 Dirichlet inverse of A083254(n), where A083254(n) = 2*phi(n) - n.

Original entry on oeis.org

1, 0, -1, 0, -3, 2, -5, 0, -2, 2, -9, 4, -11, 2, 5, 0, -15, 2, -17, 4, 7, 2, -21, 8, -6, 2, -4, 4, -27, -2, -29, 0, 11, 2, 17, 8, -35, 2, 13, 8, -39, -6, -41, 4, 8, 2, -45, 16, -10, -2, 17, 4, -51, 0, 29, 8, 19, 2, -57, 4, -59, 2, 12, 0, 35, -14, -65, 4, 23, -10, -69, 24, -71, 2, 4, 4, 47, -18, -77, 16, -8, 2, -81, -4, 47, 2, 29, 8, -87, 4

Offset: 1

Antti Karttunen, Feb 12 2019

sign

Antti Karttunen, Table of n, a(n) for n = 1..20000
Jon Maiga, Computer-generated formulas for A323912, Sequence Machine.
Wikipedia, Dirichlet convolution.

Cf. A083254, A323913.

Sequences that appear in the convolution formulas: A002033, A023900, A046692, A055615, A067824, A074206, A101035, A130054, A174725, A191161, A253249, A323910 (Möbius transform), A328722, A330575.

up_to = 16384;
DirInverse(v) = { my(u=vector(#v)); u[1] = (1/v[1]); for(n=2, #v, u[n] = (-u[1]*sumdiv(n, d, if(dA083254(n) = (2*eulerphi(n)-n);
v323912 = DirInverse(vector(up_to,n,A083254(n)));
A323912(n) = v323912[n];

A083254(n) = (2*eulerphi(n)-n);
memoA323912 = Map();
A323912(n) = if(1==n,1,my(v); if(mapisdefined(memoA323912,n,&v), v, v = -sumdiv(n,d,if(dA083254(n/d)*A323912(d),0)); mapput(memoA323912,n,v); (v))); \\ Antti Karttunen, Nov 22 2024

a(1) = 1, and for n > 1, a(n) = -Sum_{d|n, dA083254(n/d) * a(d).
From Antti Karttunen, Nov 22 2024: (Start)
Following convolution formulas were conjectured for this sequence by Sequence Machine, with each one giving the first 10000 terms correctly. The first one is certainly true, because A083254 is Möbius transform of A033879:
a(n) = Sum_{d|n} A323910(d).
a(n) = Sum_{d|n} A023900(d)*A074206(n/d) = Sum_{d|n} A002033(d-1)*A023900(n/d).
a(n) = Sum_{d|n} A055615(d)*A067824(n/d)
a(n) = Sum_{d|n} A046692(d)*A253249(n/d)
a(n) = Sum_{d|n} A130054(d)*A174725(n/d)
a(n) = Sum_{d|n} A101035(d)*A330575(n/d)
a(n) = Sum_{d|n} A191161(d)*A328722(n/d)
(End)

A338750 a(n) = 1 + Sum_{k=1..n-1} a(gcd(n,k)).

Original entry on oeis.org

1, 2, 3, 5, 5, 10, 7, 14, 13, 18, 11, 35, 13, 26, 31, 41, 17, 58, 19, 65, 45, 42, 23, 122, 41, 50, 63, 95, 29, 154, 31, 122, 73, 66, 83, 241, 37, 74, 87, 230, 41, 226, 43, 155, 193, 90, 47, 419, 85, 194, 115, 185, 53, 338, 135, 338, 129, 114, 59, 679, 61, 122, 283

Offset: 1

Ilya Gutkovskiy, Nov 06 2020

nonn

Inverse Moebius transform of A006874.

Cf. A000010, A006874, A038045, A130054.

a[n_] := a[n] = 1 + Sum[a[GCD[n, k]], {k, 1, n - 1}]; Table[a[n], {n, 1, 63}]
a[n_] := a[n] = 1 + DivisorSum[n, EulerPhi[n/#] a[#] &, # < n &]; Table[a[n], {n, 1, 63}]

G.f. A(x) satisfies: A(x) = x / (1 - x) + Sum_{k>=2} phi(k) * A(x^k).
a(n) = 1 + Sum_{d|n, d < n} phi(n/d) * a(d).
a(n) = Sum_{d|n} A006874(d).

cp's OEIS Frontend

A007431 a(n) = Sum_{d|n} phi(d)*mu(n/d).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A129691 Inverse of A054523.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A006580 a(n) = Sum_{k=1..n-1} lcm(k,n-k).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A323912 Dirichlet inverse of A083254(n), where A083254(n) = 2*phi(n) - n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A338750 a(n) = 1 + Sum_{k=1..n-1} a(gcd(n,k)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A130055 A129691 * A127093.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula