A209295 Antidiagonal sums of the gcd(.,.) array A109004.

0, 2, 5, 8, 12, 14, 21, 20, 28, 30, 37, 32, 52, 38, 53, 60, 64, 50, 81, 56, 92, 86, 85, 68, 124, 90, 101, 108, 132, 86, 165, 92, 144, 138, 133, 152, 204, 110, 149, 164, 220, 122, 237, 128, 212, 234, 181, 140, 288, 182, 245, 216, 252, 158, 297, 244

Offset: 0

Author

R. J. Mathar, Jan 17 2013

Keywords

• nonn
• easy

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 5000 terms from G. C. Greubel)

Crossrefs

Cf. A006580, A018804, A109004.

Programs

Magma

A209295:= func< n | n eq 0 select 0 else (&+[(n/d+1)*EulerPhi(d): d in Divisors(n)]) >;
[A209295(n): n in [0..40]]; // G. C. Greubel, Jun 24 2024

Maple

a:= n-> add(igcd(j, n-j), j=0..n):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 25 2019
# Alternative (computes [a(n), n=0..10000] about 25 times faster):
a := n -> add(numtheory:-phi(d)*(n/d + 1), d = numtheory:-divisors(n)):
seq(a(n), n = 0..57); # Peter Luschny, Aug 25 2019

Mathematica

Table[Sum[GCD[n-k,k], {k,0,n}], {n,0,50}] (* G. C. Greubel, Jan 04 2018 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := n + Times @@ f @@@ FactorInteger[n]; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Apr 28 2023 *)

PARI

a(n) = n + sum(k=1, n, gcd(n,k)); \\ Michel Marcus, Jan 05 2018

SageMath

def A209295(n): return sum((n/k+1)*euler_phi(k) for k in (1..n) if (k).divides(n))
[A209295(n) for n in range(41)] # G. C. Greubel, Jun 24 2024

Formula

a(0) = 0; a(n) = A018804(n) + n for n > 0. [Amended by Georg Fischer, Jan 25 2020]

a(n) = Sum_{d|n} phi(d)*(n/d + 1) for n >= 1. - Peter Luschny, Aug 25 2019