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,6

Links

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

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

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 *)

Prog

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

Crossrefs

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

Sequence in context: A322862 A325225 A206719 * A322306 A359778 A305830

Adjacent sequences: A240083 A240084 A240085 * A240087 A240088 A240089

Keyword

nonn,easy

Author

Peter Luschny, Mar 31 2014

Extensions

More terms from Antti Karttunen, Sep 23 2017

Status

approved