A390808 - OEIS

%I #18 Mar 14 2026 11:31:05

%S 1,1,3,8,10,6,21,20,36,20,55,36,78,42,60,96,136,63,171,120,126,110,

%T 253,120,275,156,270,252,406,120,465,336,330,272,420,396,666,342,468,

%U 400,820,252,903,660,630,506,1081,528,1078,525,816,936,1378,540,1100,840

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

%C The number of these integers is A206369(n).

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

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

%F 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.

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

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

%t 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]

%o (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)));}

%o (Python)

%o from math import prod

%o from sympy import factorint

%o def A390808(n):

%o     f = factorint(n)

%o     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())

%o     if any(e&1 for e in f.values()):

%o         return k>>1

%o     else:

%o         m = prod((p**(e+1)+1)//(p+1) for p,e in f.items())

%o         return k*(m+1)//(m<<1) # _Chai Wah Wu_, Mar 14 2026

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

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

%K nonn,easy

%O 1,3

%A _Amiram Eldar_, Nov 20 2025