A345305 a(n) = n * Sum_{p|n, p prime} gcd(p,n/p) / p.

0, 1, 1, 4, 1, 5, 1, 8, 9, 7, 1, 16, 1, 9, 8, 16, 1, 27, 1, 24, 10, 13, 1, 32, 25, 15, 27, 32, 1, 31, 1, 32, 14, 19, 12, 72, 1, 21, 16, 48, 1, 41, 1, 48, 54, 25, 1, 64, 49, 75, 20, 56, 1, 81, 16, 64, 22, 31, 1, 92, 1, 33, 72, 64, 18, 61, 1, 72, 26, 59, 1, 144, 1, 39, 100, 80, 18

Offset: 1

Author

Wesley Ivan Hurt, Jun 13 2021

Keywords

• nonn

Comments

If p is prime, a(p) = p * Sum_{p|p} gcd(p,p/p) / p = p * (1/p) = 1.

Examples

			a(18) = 18 * Sum_{p|18} gcd(p,18/p) / p = 18 * (gcd(2,9)/2 + gcd(3,6)/3) = 18 * (1/2 + 1) = 27.
		

Links

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

Crossrefs

Cf. A345266.

Programs

Mathematica

Table[n*Sum[(1/k) GCD[k, n/k] (PrimePi[k] - PrimePi[k - 1]) (1 - Ceiling[n/k] + Floor[n/k]), {k, n}], {n, 100}]

PARI

A345305(n) = if(1==n, 0, my(f=factor(n)); n*sum(i=1, #f~, (gcd(f[i,1],n/f[i, 1])/f[i,1]))); \\ Antti Karttunen, Jan 24 2025