A055631 Sum of Euler's totient function phi of distinct primes dividing n.

0, 1, 2, 1, 4, 3, 6, 1, 2, 5, 10, 3, 12, 7, 6, 1, 16, 3, 18, 5, 8, 11, 22, 3, 4, 13, 2, 7, 28, 7, 30, 1, 12, 17, 10, 3, 36, 19, 14, 5, 40, 9, 42, 11, 6, 23, 46, 3, 6, 5, 18, 13, 52, 3, 14, 7, 20, 29, 58, 7, 60, 31, 8, 1, 16, 13, 66, 17, 24, 11, 70, 3, 72, 37, 6, 19, 16, 15, 78, 5, 2

Offset: 1

Author

Labos Elemer, Jun 06 2000

Keywords

• nonn

Links

• G. C. Greubel, Table of n, a(n) for n = 1..5000

Crossrefs

Cf. A000010, A001221, A006093, A008472, A053570, A053571, A055632.

Programs

Maple

with(numtheory); a := n -> add(f, f = map(phi, factorset(n)));
seq(a(n), n = 1..81);  # Peter Luschny, Mar 30 2014

Mathematica

Join[{0},Table[Total[EulerPhi[Transpose[FactorInteger[n]][[1]]]],{n,2,90}]] (* Harvey P. Dale, Oct 29 2012 *)

PARI

A055631(n)=sum(i=1,#n=factor(n)~,n[1,i]-1) \\ M. F. Hasler, Nov 10 2016

Formula

a(n) = Sum_{p divides n} p-1 = A008472(n) - A001221(n).

If n = p^w, a power of prime, then a(n) = p-1; if n = 2p, then a(n) = p = n/2.

Additive with a(p^e) = p-1: a(10) = a(2*5) = a(2)+a(5) = (2-1)+(5-1) = 5; a(28) = a(2^2*7) = a(2^2)+a(7) = 1+6 = 7. - Vladeta Jovovic, Oct 23 2001

G.f.: Sum_{k>=1} (prime(k) - 1) * x^prime(k) / (1 - x^prime(k)). - Ilya Gutkovskiy, Aug 18 2021

Extensions

Edited by M. F. Hasler, Nov 10 2016