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

1, 3, 3, 10, 10, 12, 21, 36, 27, 40, 55, 48, 78, 84, 60, 136, 136, 108, 171, 160, 126, 220, 253, 192, 250, 312, 243, 336, 406, 240, 465, 528, 330, 544, 420, 432, 666, 684, 468, 640, 820, 504, 903, 880, 540, 1012, 1081, 768, 1029, 1000, 816, 1248, 1378, 972, 1100

Offset

1,2

Comments

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

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Formula

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

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

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.

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

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

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

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

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

Mathematica

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]

Prog

(PARI) a(n) = {my(e = valuation(n, 2)); if(n >> e == 1, 2^(e-1)*(2^e+1), eulerphi(2*n)*n/2); }
(Python)
from sympy import totient
def A390804(n): return totient(n<<1)*n>>1 if (n&-n)^n else n*(n+1)>>1 # Chai Wah Wu, Mar 14 2026

Crossrefs

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

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).

Sequence in context: A134704 A057210 A330632 * A278832 A168376 A266221

Adjacent sequences: A390801 A390802 A390803 * A390805 A390806 A390807

Keyword

nonn,easy

Author

Amiram Eldar, Nov 20 2025

Status

approved