A240086 a(n) = Sum_{prime p|n} phi(gcd(p, n/p)) where phi is Euler's totient function.

0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 2, 4, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 3, 2, 1, 2, 6, 5, 2, 2, 1, 3, 2, 2, 2, 2, 1, 3, 1, 2, 3, 1, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 5, 2, 2, 3, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 1, 4, 2, 2, 2, 2, 2, 2, 1, 7, 3, 5, 1, 3, 1, 2, 3

Offset: 1

Author

Peter Luschny, Mar 31 2014

Keywords

• nonn
• easy

Links

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

Crossrefs

Cf. A000010, A001616, A010051, A001248, A006093.

Programs

Maple

with(numtheory): a := n -> add(phi(igcd(d, n/d)), d = factorset(n)); seq(a(n), n=1..100);

Mathematica

a[n_] := Sum[EulerPhi[GCD[p, n/p]], {p, FactorInteger[n][[;;, 1]]}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Aug 29 2023 *)

PARI

A240086(n) = sumdiv(n,p,(isprime(p)*eulerphi(gcd(p, n/p)))); \\ Antti Karttunen, Sep 23 2017

Formula

If n = p^2 for some prime p then a(n) = p - 1 and a(k) <= a(n) for k <= n. - Peter Luschny, Sep 05 2023

Extensions

More terms from Antti Karttunen, Sep 23 2017