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

1, 3, 6, 10, 15, 15, 28, 36, 45, 45, 66, 60, 91, 91, 105, 136, 153, 135, 190, 180, 210, 231, 276, 240, 325, 325, 378, 364, 435, 330, 496, 528, 528, 561, 595, 540, 703, 703, 741, 720, 861, 672, 946, 924, 945, 1035, 1128, 960, 1225, 1125, 1275, 1300, 1431, 1215, 1485

Offset

1,2

Comments

The number of these integers is A131233(n).

Links

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

Formula

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

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

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

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).

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

Mathematica

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]

Prog

(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);

Crossrefs

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

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).

Sequence in context: A259604 A130484 A074374 * A109804 A231672 A375750

Adjacent sequences: A390797 A390798 A390799 * A390801 A390802 A390803

Keyword

nonn,easy

Author

Amiram Eldar, Nov 20 2025

Status

approved