A063754 Dirichlet convolution of totient and cototient.

0, 1, 1, 3, 1, 7, 1, 8, 5, 11, 1, 20, 1, 15, 13, 20, 1, 31, 1, 32, 17, 23, 1, 52, 9, 27, 21, 44, 1, 71, 1, 48, 25, 35, 21, 88, 1, 39, 29, 84, 1, 99, 1, 68, 61, 47, 1, 128, 13, 83, 37, 80, 1, 123, 29, 116, 41, 59, 1, 200, 1, 63, 81, 112, 33, 155, 1, 104, 49, 159, 1, 228, 1, 75, 101

Offset: 1

Author

Labos Elemer, Aug 14 2001

Keywords

• easy
• nonn
• look

Comments

a(n) = 1 if and only if n is prime. - Robert Israel, Feb 04 2018

a(n) = n+1 if and only if n = 2*p with p an odd prime (A100484 \ {4}). - Bernard Schott, Jun 19 2023

Examples

			n = 24: divisors = {1, 2, 3, 4, 6, 8, 12, 24}, d-phi(d) = {0, 1, 1, 2, 4, 4, 8, 16}, phi(n/d) = {8, 4, 4, 2, 2, 2, 1, 1}, products = {0, 4, 4, 4, 8, 8, 8, 16}, a(24) = 52.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A018804, A029935, A051953, A100484.

Cf. A001620, A013661, A306016.

Programs

Maple

f:= n -> add(numtheory:-phi(d)*(n/d - numtheory:-phi(n/d)), d=numtheory:-divisors(n)):
map(f, [$1..100]); # Robert Israel, Feb 04 2018

Mathematica

f1[p_, e_] := (e*(p - 1)/p + 1)*p^e; f2[p_, e_] := (e+1)*(p^e - p^(e-1)) - (e-1)*(p^(e-1) - p^(e-2)); a[n_] := Times @@ f1 @@@ (fct = FactorInteger[n]) - Times @@ f2 @@@ fct; a[1] = 0; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

PARI

a(n) = sumdiv(n, d, eulerphi(d)*(n/d - eulerphi(n/d))); \\ Michel Marcus, Feb 05 2018

Formula

a(n) = Sum_{d|n} A000010(d)*A051953(n/d).

From Richard L. Ollerton, May 06 2021: (Start)

a(n) = Sum_{k=1..n} A051953(gcd(n,k)).

a(n) = Sum_{k=1..n} A051953(n/gcd(n,k))*A000010(gcd(n,k))/A000010(n/gcd(n,k)).

a(n) = A018804(n) - A029935(n). (End)

Sum_{k=1..n} a(k) ~ (1/(2*zeta(2)))*(1 - 1/zeta(2)) * n^2 * (log(n) + 2*gamma - 1/2 - ((zeta(2)-2)/(zeta(2)-1))*(zeta'(2)/zeta(2))), where gamma is Euler's constant (A001620). - Amiram Eldar, Jan 11 2024

Extensions

Offset corrected by Robert Israel, Feb 04 2018