A390806 The sum of the integers k from 1 to n such that gcd(n, k) is squarefree (A005117).

1, 3, 6, 6, 15, 21, 28, 24, 36, 55, 66, 54, 91, 105, 120, 96, 153, 144, 190, 150, 231, 253, 276, 216, 300, 351, 324, 294, 435, 465, 496, 384, 561, 595, 630, 432, 703, 741, 780, 600, 861, 903, 946, 726, 900, 1081, 1128, 864, 1176, 1200, 1326, 1014, 1431, 1296, 1540

Offset

1,2

Comments

The number of these integers is A063659(n).

Links

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

Formula

a(n) = Sum_{k=1..n, gcd(k,n) is squarefree} k = Sum_{k=1..n} A008966(gcd(k,n)) * k.

a(n) = (n + A008966(n)) * A063659(n) / 2.

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

a(n) <= A390807(n), with equality if and only if n is squarefree.

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

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

Mathematica

f[p_, e_] := If[e == 1, p, p^e - p^(e-2)]; a[n_] := Module[{fct = FactorInteger[n]}, (n + Boole[Max[fct[[;; , 2]]] == 1]) * Times @@ f @@@ fct]/2; Array[a, 100]

Prog

(PARI) a(n) = {my(f = factor(n)); (n + issquarefree(f)) * prod(i = 1, #f~, if(f[i, 2] == 1, f[i, 1], f[i, 1]^f[i, 2] - f[i, 1]^(f[i, 2]-2))) / 2; }

Crossrefs

Cf. A005117, A008966, A063659.

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), this sequence (squarefree), A390807 (cubefree), A390808 (square), A390809 (1 or 2).

Sequence in context: A238775 A269525 A341885 * A364372 A036252 A103463

Adjacent sequences: A390803 A390804 A390805 * A390807 A390808 A390809

Keyword

nonn,easy

Author

Amiram Eldar, Nov 20 2025

Status

approved