A390804 - OEIS

%I #12 Mar 14 2026 11:30:58

%S 1,3,3,10,10,12,21,36,27,40,55,48,78,84,60,136,136,108,171,160,126,

%T 220,253,192,250,312,243,336,406,240,465,528,330,544,420,432,666,684,

%U 468,640,820,504,903,880,540,1012,1081,768,1029,1000,816,1248,1378,972,1100

%N The sum of the integers k from 1 to n such that gcd(n, k) is a power of 2.

%C The number of these integers is phi(2*n) = A062570(n).

%H Amiram Eldar, <a href="/A390804/b390804.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{k=1..n, gcd(k,n) is power of 2} k = Sum_{k=1..n} A209229(gcd(k,n)) * k.

%F a(n) = (A062570(n) + A209229(n)) * n/2.

%F a(n) = A007582(e) = 2^(e-1)*(2^e+1) if n = 2^e is a power of 2 (A000079), and a(n) = phi(2*n)*n/2 otherwise.

%F a(n) >= A023896(n), with equality if and only if n is odd.

%F a(n) <= n*(n+1)/2, with equality if and only if n is a power of 2.

%F a(n) >= A390809(n), with equality if and only if n is not a multiple of 4 (A042968).

%F Dirichlet g.f.: (zeta(s-2)/zeta(s-1) + 1) / (2 - 1/2^(s-2)).

%F Sum_{k=1..n} a(k) ~ (4/(3*Pi^2)) * n^3.

%t a[n_] := Module[{e = IntegerExponent[n, 2]}, If[n == 2^e, 2^(e-1)*(2^e+1), EulerPhi[2*n]*n/2]]; Array[a, 100]

%o (PARI) a(n) = {my(e = valuation(n, 2)); if(n >> e == 1, 2^(e-1)*(2^e+1), eulerphi(2*n)*n/2);}

%o (Python)

%o from sympy import totient

%o def A390804(n): return totient(n<<1)*n>>1 if (n&-n)^n else n*(n+1)>>1 # _Chai Wah Wu_, Mar 14 2026

%Y Cf. A000010 (phi), A000079, A007582, A042968, A062570, A209229.

%Y The sum of the integers k from 1 to n such that gcd(n, k) is: A023896 (1), A119790 (prime power, A246655), A390800 (power of prime, A000961), A390801 (prime), A390802 (odd), A390803 (5-rough), this sequence (power of 2), A390805 (3-smooth), A390806 (squarefree), A390807 (cubefree), A390808 (square), A390809 (1 or 2).

%K nonn,easy

%O 1,2

%A _Amiram Eldar_, Nov 20 2025