A127416 a(n) = Sum_{1<=k<=n, gcd(k,n)=1} (Sum_{i=1..k} gcd(i, k)).

1, 1, 4, 6, 17, 10, 41, 28, 54, 40, 122, 44, 183, 82, 130, 140, 340, 102, 436, 156, 304, 254, 673, 184, 665, 360, 604, 388, 1143, 232, 1335, 584, 854, 656, 1138, 484, 1997, 842, 1238, 768, 2486, 508, 2762, 1044, 1382, 1314, 3339, 816, 3139, 1160, 2276, 1600

Offset

1,3

Comments

a(n) = Sum_{1<=k<=n, gcd(k,n)=1} A018804(k) where A018804(n) = Sum_{k=1..n} gcd(k,n).

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Formula

M * V where M = A054521 is an infinite lower triangular matrix and V = A018804 is a vector: (1, 3, 5, 8, 9, 15, 13, ...).

Example

a(6) = 10 since the relative primes of 6 are 1 and 5, A018804(1) + A018804(5) = 1 + 9 = 10.

Mathematica

f[p_, e_] := (e*(p - 1)/p + 1)*p^e; pil[n_] := Times @@ (f @@@ FactorInteger[n]); a[n_] := Sum[If[GCD[n, k] == 1, pil[k], 0], {k, 1, n}]; Array[a, 100] (* Amiram Eldar, Jul 19 2019 *)

Prog

(PARI) f(n) = sum(i=1, n, gcd(n, i)); \\ A018804
a(n) = sum(k=1, n, if (gcd(k, n) == 1, f(k))); \\ Michel Marcus, Jul 19 2019

Crossrefs

Cf. A018804, A054521.

Sequence in context: A083009 A365111 A190968 * A306017 A226631 A226634

Adjacent sequences: A127413 A127414 A127415 * A127417 A127418 A127419

Keyword

nonn

Author

Gary W. Adamson, Jan 13 2007

Extensions

More terms from Amiram Eldar, Jul 19 2019

Status

approved