A345891 a(n) = n + (n - 1) * phi(n).

1, 3, 7, 10, 21, 16, 43, 36, 57, 46, 111, 56, 157, 92, 127, 136, 273, 120, 343, 172, 261, 232, 507, 208, 505, 326, 495, 352, 813, 262, 931, 528, 673, 562, 851, 456, 1333, 704, 951, 664, 1641, 534, 1807, 904, 1101, 1036, 2163, 800, 2065, 1030, 1651, 1276, 2757, 1008, 2215, 1376

Offset: 1

Author

Wesley Ivan Hurt, Jun 28 2021

Keywords

• nonn

Comments

For 1 <= k <= n, add n if gcd(n,k) = 1, otherwise add 1. For n = 9 there are 6 numbers less than or equal to 9 that are relatively prime to 9 and 3 that are not. So a(9) = 9*6 + 3*1 = 57.

Crossrefs

Cf. A000010 (phi), A062955, A345892.

Programs

Mathematica

Table[n + (n - 1)*EulerPhi[n], {n, 50}]

PARI

a(n) = n + (n-1)*eulerphi(n); \\ Michel Marcus, Jun 28 2021

Formula

a(n) = Sum_{k=1..n} n^floor(1/gcd(n,k)).

a(n) = A062955(n) + n. - Michel Marcus, Jun 28 2021