A343490 - OEIS

%I #18 Sep 11 2023 17:52:38

%S 1,5,18,70,260,1050,4102,16460,65574,262420,1048586,4195500,16777228,

%T 67112990,268436040,1073758360,4294967312,17179936830,68719476754,

%U 274878169880,1099511636076,4398047559730,17592186044438,70368748407000,281474976711700,1125899923619900

%N a(n) = Sum_{k=1..n} 4^(gcd(k, n) - 1).

%H Robert Israel, <a href="/A343490/b343490.txt">Table of n, a(n) for n = 1..1660</a>

%F a(n) = Sum_{d|n} phi(n/d)*4^(d - 1) = A054611(n)/4.

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

%p N:= 30: # for a(1)..a(N)

%p G:= add(numtheory:-phi(k)*x^k/(1-4*x^k),k=1..N):

%p S:= series(G,x,N+1):

%p seq(coeff(S,x,j),j=1..N); # _Robert Israel_, Sep 11 2023

%t a[n_] := Sum[4^(GCD[k, n] - 1), {k, 1, n}]; Array[a, 26] (* _Amiram Eldar_, Apr 17 2021 *)

%o (PARI) a(n) = sum(k=1, n, 4^(gcd(k, n)-1));

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

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

%Y Column 4 of A343489.

%Y Cf. A000010, A054611.

%K nonn

%O 1,2

%A _Seiichi Manyama_, Apr 17 2021