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,2

Links

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

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

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

Prog

(PARI) a(n) = n + sum(k=1, n, gcd(n, k)); \\ Michel Marcus, Jan 05 2018
(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
(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

Crossrefs

Cf. A006580, A018804, A109004.

Sequence in context: A189531 A190347 A193767 * A184813 A108311 A092767

Adjacent sequences: A209292 A209293 A209294 * A209296 A209297 A209298

Keyword

nonn,easy

Author

R. J. Mathar, Jan 17 2013

Status

approved