A092693 Sum of iterated phi(n).

0, 1, 3, 3, 7, 3, 9, 7, 9, 7, 17, 7, 19, 9, 15, 15, 31, 9, 27, 15, 19, 17, 39, 15, 35, 19, 27, 19, 47, 15, 45, 31, 35, 31, 39, 19, 55, 27, 39, 31, 71, 19, 61, 35, 39, 39, 85, 31, 61, 35, 63, 39, 91, 27, 71, 39, 55, 47, 105, 31, 91, 45, 55, 63, 79, 35, 101, 63, 79, 39, 109, 39, 111

Offset: 1

Author

T. D. Noe, Mar 04 2004

Keywords

• nonn

Comments

Iannucci, Moujie and Cohen examine perfect totient numbers: n such that a(n) = n.

Examples

			a(100) = 71 because the iterations of phi (40, 16, 8, 4, 2, 1) sum to 71.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• C. Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq. 18 (2015) # 15.2.1
• P. Erdos and M. V. Subbarao, On the iterates of some arithmetic functions, The theory of arithmetic functions (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich. 1971), Lecture Notes in Math., 251 , pp. 119-125, Springer, Berlin, 1972. [alternate link]
• Douglas E. Iannucci, Deng Moujie and Graeme L. Cohen, On perfect totient numbers, J. Integer Sequences, 6 (2003), #03.4.5.

Crossrefs

Cf. A003434 (iterations of phi(n) needed to reach 1), A092694 (iterated phi product).

Cf. A082897 and A091847 (perfect totient numbers).

Programs

Haskell

a092693 1 = 0
a092693 n = (+ 1) $ sum $ takeWhile (/= 1) $ iterate a000010 $ a000010 n
-- Reinhard Zumkeller, Oct 27 2011

Mathematica

nMax=100; a=Table[0, {nMax}]; Do[e=EulerPhi[n]; a[[n]]=e+a[[e]], {n, 2, nMax}]; a (* T. D. Noe *)
Table[Plus @@ FixedPointList[EulerPhi, n] - (n + 1), {n, 72}] (* Alonso del Arte, Jan 29 2007 *)

PARI

a(n)=my(k);while(n>1,k+=n=eulerphi(n));k \\ Charles R Greathouse IV, Mar 22 2012

Python

from sympy import totient
from math import prod
def f(n):
    m = n
    while m > 1:
        m = totient(m)
        yield m
def A092693(n): return sum(f(n)) # Chai Wah Wu, Nov 14 2021

Formula

a(1) = 0, a(n) = phi(n) + a(phi(n))

a(n) = A053478(n) - n. - Vladeta Jovovic, Jul 02 2004

Erdős & Subbarao prove that a(n) ~ phi(n) for almost all n. In particular, a(n) < n for almost all n. The proportion of numbers up to N for which a(n) > n is at most 1/log log log log N. - Charles R Greathouse IV, Mar 22 2012