OFFSET
1,3
COMMENTS
The number of these integers is A026741(n).
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0,3,0,-3,0,1).
FORMULA
a(n) = Sum_{k=1..n, gcd(k,n) odd} k = Sum_{k=1..n} A000035(gcd(k,n)) * k.
a(n) = n*(n+1)/2 if n is odd, and n^2/4 if n is even.
a(n) = n * (2 - 2*(-1)^n + 3*n - (-1)^n*n) / 8.
a(n) = A367204(n+2) - 1.
G.f.: x * (x^3 + 3*x^2 + x + 1)/(1 - x^2)^3.
E.g.f.: (x/4) * ((x+4) * cosh(x) + (2*x+1) * sinh(x)).
Dirichlet g.f.: (zeta(s-2) + zeta(s-1)) * (1 - 1/2^(s-1)) / 2.
a(n) >= A023896(n), with equality if and only if n is a power of 2.
Sum_{k=1..n} a(k) ~ n^3 / 8.
MATHEMATICA
a[n_] := n * If[EvenQ[n], n/2, n + 1]/2; Array[a, 100]
PROG
(PARI) a(n) = if(n%2, n*(n+1)/2, n^2/4);
(Python)
def A390802(n): return n*(n+1)>>1 if n&1 else n**2>>2 # Chai Wah Wu, Mar 14 2026
CROSSREFS
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), this sequence (odd), A390803 (5-rough), A390804 (power of 2), A390805 (3-smooth), A390806 (squarefree), A390807 (cubefree), A390808 (square), A390809 (1 or 2).
KEYWORD
nonn,easy
AUTHOR
Amiram Eldar, Nov 20 2025
STATUS
approved
