A122411 a(n) is the sum of primes p for those k's, 2 <= k <= n, where gcd(k,n) = p^j > 1. (a(1) = 0.)

0, 2, 3, 4, 5, 7, 7, 8, 9, 13, 11, 14, 13, 19, 22, 16, 17, 21, 19, 26, 32, 31, 23, 28, 25, 37, 27, 38, 29, 38, 31, 32, 52, 49, 58, 42, 37, 55, 62, 52, 41, 56, 43, 62, 66, 67, 47, 56, 49, 65, 82, 74, 53, 63, 94, 76, 92, 85, 59, 76, 61, 91, 96, 64, 112, 92, 67, 98, 112, 106, 71

Offset: 1

Author

Leroy Quet, Sep 02 2006

Keywords

• nonn

Examples

			The integers k, 2 <= k <= 12, where gcd(k,12) is a power of a prime are 2,3,4,8,9 and 10. gcd(2,12) = 2^1, gcd(3,12) = 3^1, gcd(4,12) = 2^2, gcd(8, 12) = 2^2, gcd(9,12) = 3^1 and gcd(10,12) = 2^1. The sum of the prime bases of the prime-powers is 2+3+2+2+3+2 = 14. So a(12) = 14.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537

Crossrefs

Cf. A020639, A122410.

Programs

Maple

with(numtheory): a:= proc(n) local k, m := 0; for k from 2 to n do if nops(factorset(gcd(n, k))) = 1 then m:= m + factorset(gcd(n, k))[1]; end if; end do; return m; end proc: seq(a(n), n=1..80); # Ridouane Oudra, Feb 03 2023

Mathematica

f[n_] := Plus @@ First /@ Flatten[Select[FactorInteger[GCD[Range[n], n]], Length[ # ] == 1 &], 1]; Table[f[n], {n, 80}] (* Ray Chandler, Sep 06 2006 *)
a[n_] := Module[{p = FactorInteger[n][[;;, 1]]}, n * Times @@ (1 - 1/p) * Total[p/(p-1)]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 22 2025 *)

PARI

A122411(n) = { my(p=0); sum(k=2,n,if(isprimepower(gcd(n,k),&p),p,0)); }; \\ Antti Karttunen, Feb 25 2018

PARI

a(n) = {my(f = factor(n), p = f[,1]);  eulerphi(f) * vecsum(apply(x -> x/(x-1), p));} \\ Amiram Eldar, Jun 22 2025

Formula

a(n) = phi(n) * Sum_{p|n} p/(p-1), where p is prime. - Ridouane Oudra, Feb 03 2023

a(n) = Sum_{d|n, d is a prime power} A020639(d)*phi(n/d). - Ridouane Oudra, Feb 13 2023

a(n) = Sum_{p|n, p prime} p^v(n,p)*phi(n/p^v(n,p)), where p^v(n,p) is the highest power of p dividing n. - Ridouane Oudra, Oct 06 2023

Extensions

Corrected and extended by Ray Chandler, Sep 06 2006