A122410 a(n) = sum of j's for those k's, 1 <= k <= n, where gcd(k,n) = p^j, p = prime.

0, 1, 1, 3, 1, 3, 1, 7, 4, 5, 1, 8, 1, 7, 6, 15, 1, 10, 1, 14, 8, 11, 1, 18, 6, 13, 13, 20, 1, 14, 1, 31, 12, 17, 10, 26, 1, 19, 14, 32, 1, 20, 1, 32, 22, 23, 1, 38, 8, 26, 18, 38, 1, 31, 14, 46, 20, 29, 1, 36, 1, 31, 30, 63, 16, 32, 1, 50, 24, 34, 1, 58, 1, 37, 32, 56, 16, 38, 1, 68, 40

Offset

1,4

Links

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

Example

The positive integers k, k <= 12, where gcd(k,12) = a power of a prime, are 1, 2, 3, 4, 8, 9 and 10; gcd(1,12) = p^0, 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 exponents raising the primes is 0+1+1+2+2+1+1 = 8. So a(12) = 8.

Mathematica

f[n_] := Plus @@ Last /@ Flatten[Select[FactorInteger[GCD[Range[n], n]], Length[ # ] == 1 &], 1]; Table[f[n], {n, 80}] (* Ray Chandler, Sep 06 2006 *)

Prog

(PARI) A122410(n) = sum(k=1, n, isprimepower(gcd(n, k))); \\ Antti Karttunen, Feb 25 2018

Crossrefs

Cf. A122411.

Sequence in context: A218403 A318506 A322382 * A309790 A349619 A082495

Adjacent sequences: A122407 A122408 A122409 * A122411 A122412 A122413

Keyword

nonn

Author

Leroy Quet, Sep 02 2006

Extensions

Extended by Ray Chandler, Sep 06 2006

Status

approved