A390800 - OEIS

%I #9 Nov 20 2025 04:00:10

%S 1,3,6,10,15,15,28,36,45,45,66,60,91,91,105,136,153,135,190,180,210,

%T 231,276,240,325,325,378,364,435,330,496,528,528,561,595,540,703,703,

%U 741,720,861,672,946,924,945,1035,1128,960,1225,1125,1275,1300,1431,1215,1485

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

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

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

%F a(n) = Sum_{k=1..n, gcd(k,n) is in A000961} k = Sum_{k=1..n} A010055(gcd(k,n)) * k.

%F a(n) = A023896(n) + A119790(n) for n >= 2.

%F a(n) = (n + A010055(n)) * A131233(n) / 2.

%F Dirichlet g.f.: (zeta(s-2)/zeta(s-1) + 1) * A(s-1) / 2, where A(s) = Sum_{n>=1} A010055(n)/n^s = 1 + Sum_{p prime} 1/(p^s-1).

%F Sum_{k=1..n} a(k) ~ c * n^3 / 6, where c = (1 + Sum_{p prime} (1/(p^2-1))) / zeta(2) = (1 + A154945)/A013661 = 0.94331640941093700227... .

%t a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, If[Length[p] == 1, n + 1, n] * n * Times @@ (1 - 1/p) * (1 + Total[1/(p - 1)])/2]; a[1] = 1; Array[a, 100]

%o (PARI) a(n) = if(n == 1, 1 , my(f = factor(n), p = f[,1]); (n + if(#p == 1, 1, 0)) * n * prod(i = 1, #p, 1 - 1/p[i]) * (1 + sum(i = 1, #p, 1/(p[i] - 1))) / 2);

%Y Cf. A000961, A010055, A013661, A131233, A154945.

%Y The sum of the integers k from 1 to n such that gcd(n, k) is: A023896 (1), A119790 (prime power, A246655), this sequence (power of prime, A000961), A390801 (prime), A390802 (odd), A390803 (5-rough), A390804 (power of 2), A390805 (3-smooth), A390806 (squarefree), A390807 (cubefree), A390808 (square), A390809 (1 or 2).

%K nonn,easy

%O 1,2

%A _Amiram Eldar_, Nov 20 2025