login
a(n) = Sum_{d|n} phi(d) * binomial(d+n/d-1, d).
0

%I #22 May 09 2021 11:44:26

%S 1,3,5,9,9,22,13,32,35,53,21,121,25,96,177,166,33,297,37,491,417,218,

%T 45,1002,549,297,705,1375,57,2418,61,1640,1405,491,3887,4659,73,606,

%U 2233,8156,81,8989,85,6189,11955,872,93,16550,10387,12927,4757,11111,105,22392,25757

%N a(n) = Sum_{d|n} phi(d) * binomial(d+n/d-1, d).

%F G.f.: Sum_{k >= 1} phi(k) * x^k/(1 - x^k)^(k+1).

%F If p is prime, a(p) = 2*p - 1.

%F From _Richard L. Ollerton_, May 07 2021: (Start)

%F a(n) = Sum_{k=1..n} binomial(gcd(n,k) + n/gcd(n,k) - 1,n/gcd(n,k)).

%F 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)

%t a[n_] := DivisorSum[n, EulerPhi[#] * Binomial[# + n/# - 1, #] &]; Array[a, 100] (* _Amiram Eldar_, Apr 22 2021 *)

%o (PARI) a(n) = sumdiv(n, d, eulerphi(d)*binomial(d+n/d-1, d));

%o (PARI) my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*x^k/(1-x^k)^(k+1)))

%Y Cf. A000010, A156834, A343517, A338658.

%K nonn

%O 1,2

%A _Seiichi Manyama_, Apr 22 2021