login
a(n) = Sum_{d divides n} phi(d)*phi(n/d).
37

%I #46 Jan 05 2024 00:01:31

%S 1,2,4,5,8,8,12,12,16,16,20,20,24,24,32,28,32,32,36,40,48,40,44,48,56,

%T 48,60,60,56,64,60,64,80,64,96,80,72,72,96,96,80,96,84,100,128,88,92,

%U 112,120,112,128,120,104,120

%N a(n) = Sum_{d divides n} phi(d)*phi(n/d).

%C Dirichlet convolution of A000010 with itself. - _R. J. Mathar_, Aug 28 2015

%H Gheorghe Coserea, <a href="/A029935/b029935.txt">Table of n, a(n) for n = 1..20000</a>

%F From _Vladeta Jovovic_, Oct 30 2001: (Start)

%F Sum_{k=1..n} phi(gcd(n, k)).

%F Multiplicative with a(p^e) = (e+1)*(p^e - p^(e - 1)) - (e - 1)*(p^(e - 1) - p^(e - 2)). (End)

%F From _Franklin T. Adams-Watters_, Nov 19 2004: (Start)

%F Sum_{d|n} a(d) = A018804(n), Mobius transform of A018804.

%F Dirichlet g.f.: zeta(s-1)^2/zeta(s)^2. (End)

%F Equals row sums of triangle A143258. - _Gary W. Adamson_, Aug 02 2008

%F a(n) <= A000010(n) * A000005(n), with equality iff n = A005117(k) for some k. - _Gheorghe Coserea_, Oct 23 2016

%F Sum_{k=1..n} a(k) ~ 9*n^2 * ((2*log(n) + 4*gamma - 1)/Pi^4 - 24*Zeta'(2)/Pi^6), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Jan 31 2019

%p with(numtheory): A029935 := proc(n) local i,j; j := 0; for i in divisors(n) do j := j+phi(i)*phi(n/i); od; j; end;

%t A029935[n_]:=DivisorSum[n,EulerPhi[#]*EulerPhi[n/#]&]; Array[A029935, 50]

%t f[p_, e_] := (e+1)*(p^e - p^(e-1)) - (e-1)*(p^(e-1) - p^(e-2)); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Apr 26 2023 *)

%o (PARI)

%o a(n) = {

%o my(f = factor(n), fsz = matsize(f)[1],

%o g = prod(k=1, fsz, f[k,1]),

%o h = prod(k=1, fsz, sqr(f[k,1]-1)*f[k,2] + sqr(f[k,1])-1));

%o return(h*n\sqr(g));

%o };

%o vector(54, n, a(n)) \\ _Gheorghe Coserea_, Oct 23 2016

%o (PARI) a(n) = sumdiv(n, d, eulerphi(d)*eulerphi(n/d)); \\ _Michel Marcus_, Oct 23 2016

%Y Cf. A000005, A000010, A001620, A005117, A018804, A029936, A143258.

%Y Row sums of A159937.

%K mult,nonn

%O 1,2

%A _N. J. A. Sloane_