A390808 The sum of the integers k from 1 to n such that gcd(n, k) is a square.

1, 1, 3, 8, 10, 6, 21, 20, 36, 20, 55, 36, 78, 42, 60, 96, 136, 63, 171, 120, 126, 110, 253, 120, 275, 156, 270, 252, 406, 120, 465, 336, 330, 272, 420, 396, 666, 342, 468, 400, 820, 252, 903, 660, 630, 506, 1081, 528, 1078, 525, 816, 936, 1378, 540, 1100, 840

Offset

1,3

Comments

The number of these integers is A206369(n).

Links

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

Formula

a(n) = Sum_{k=1..n, gcd(k,n) is square} k = Sum_{k=1..n} A010052(gcd(k,n)) * k.

a(n) = n * (1 + f(n)) * A206369(n) / 2, where f(n) = 1/A057660(sqrt(n)) if n is a square, and f(n) = 0 otherwise.

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

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

Mathematica

f1[p_, e_] := Sum[(-1)^(e - k)*p^k, {k, 0, e}]; f2[p_, e_] := (p^(e + 1) + 1)/(p + 1); a[1] = 1; a[n_] := Module[{fct = FactorInteger[n]}, (n/2) * (Times @@ f1 @@@ fct) * If[AllTrue[fct[[;; , 2]], EvenQ], (1 + 1/(Times @@ f2 @@@ fct)), 1]]; Array[a, 100]

Prog

(PARI) a(n) = {my(f = factor(n), p, e); (n/2) * prod(i = 1, #f~, p = f[i, 1]; e = f[i, 2]; sum(k = 0, e, (-1)^(e-k) * p^k)) * if(vecsum(apply(x->x%2, f[, 2])), 1, 1 + 1/prod(i = 1, #f~, (f[i, 1]^(f[i, 2] + 1) + 1)/(f[i, 1] + 1))); }
(Python)
from math import prod
from sympy import factorint
def A390808(n):
    f = factorint(n)
    k = n*prod((lambda x:x[0]+int((x[1]<<1)>=p+1))(divmod(p**(e+1), p+1)) for p, e in f.items())
    if any(e&1 for e in f.values()):
        return k>>1
    else:
        m = prod((p**(e+1)+1)//(p+1) for p, e in f.items())
        return k*(m+1)//(m<<1) # Chai Wah Wu, Mar 14 2026

Crossrefs

Cf. A000290, A005117, A010052, A057660, A206369.

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), A390804 (power of 2), A390805 (3-smooth), A390806 (squarefree), A390807 (cubefree), this sequence (square), A390809 (1 or 2).

Sequence in context: A095866 A067569 A127518 * A176118 A151693 A007284

Adjacent sequences: A390805 A390806 A390807 * A390809 A390810 A390811

Keyword

nonn,easy

Author

Amiram Eldar, Nov 20 2025

Status

approved