A345965 a(1) = 1; for n>1, a(n) = phi(n) + a(n/p) where p is the least prime divisor of n.

1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 9, 13, 13, 13, 16, 17, 15, 19, 17, 19, 21, 23, 17, 25, 25, 27, 25, 29, 21, 31, 32, 31, 33, 31, 27, 37, 37, 37, 33, 41, 31, 43, 41, 37, 45, 47, 33, 49, 45, 49, 49, 53, 45, 51, 49, 55, 57, 59, 37, 61, 61, 55, 64, 61, 51, 67, 65, 67, 55

Offset: 1

Author

Michel Marcus, Jun 30 2021

Keywords

• nonn

Links

• Peter Cameron, A new constant?, May 23 2021.

Crossrefs

Cf. A000010, A032742.

Programs

Maple

a:= proc(n) option remember; uses numtheory;
      `if`(n=1, 1, phi(n)+a(n/min(factorset(n))))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Jun 30 2021

Mathematica

a[1] = 1; a[n_] := a[n] = EulerPhi[n] + a[n/FactorInteger[n][[1, 1]]]; Array[a, 100] (* Amiram Eldar, Jun 30 2021 *)

PARI

a(n) = if (n==1, 1, eulerphi(n) + a(n/vecmin(factor(n)[,1])));

Python

from sympy import primefactors, totient as phi
def a(n): return 1 if n == 1 else phi(n) + a(n//min(primefactors(n)))
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jun 30 2021

Formula

a(p) = p for prime p.

a(n) = Sum_{k=0..bigomega(n)} phi(F^k(n)), where F^k(n) is the k-th iterate of F(n) = A032742(n). - Ridouane Oudra, Mar 17 2024