A390806 - OEIS

%I #10 Nov 20 2025 04:01:52

%S 1,3,6,6,15,21,28,24,36,55,66,54,91,105,120,96,153,144,190,150,231,

%T 253,276,216,300,351,324,294,435,465,496,384,561,595,630,432,703,741,

%U 780,600,861,903,946,726,900,1081,1128,864,1176,1200,1326,1014,1431,1296,1540

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

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

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

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

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

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

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

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

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

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

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

%Y Cf. A005117, A008966, A063659.

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

%K nonn,easy

%O 1,2

%A _Amiram Eldar_, Nov 20 2025