A338655 a(n) = Sum_{d|n} phi(d) * binomial(d+n/d-1, d).
1, 3, 5, 9, 9, 22, 13, 32, 35, 53, 21, 121, 25, 96, 177, 166, 33, 297, 37, 491, 417, 218, 45, 1002, 549, 297, 705, 1375, 57, 2418, 61, 1640, 1405, 491, 3887, 4659, 73, 606, 2233, 8156, 81, 8989, 85, 6189, 11955, 872, 93, 16550, 10387, 12927, 4757, 11111, 105, 22392, 25757
Offset: 1
Keywords
Programs
-
Mathematica
a[n_] := DivisorSum[n, EulerPhi[#] * Binomial[# + n/# - 1, #] &]; Array[a, 100] (* Amiram Eldar, Apr 22 2021 *)
-
PARI
a(n) = sumdiv(n, d, eulerphi(d)*binomial(d+n/d-1, d));
-
PARI
my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k/(1-x^k)^(k+1)))
Formula
G.f.: Sum_{k >= 1} phi(k) * x^k/(1 - x^k)^(k+1).
If p is prime, a(p) = 2*p - 1.
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} binomial(gcd(n,k) + n/gcd(n,k) - 1,n/gcd(n,k)).
a(n) = Sum_{k=1..n} binomial(gcd(n,k) + n/gcd(n,k) - 1,gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)