A060607 Number of iterations of phi(x) at prime(n) needed to reach 1.

1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 6, 8, 7, 8, 7, 7, 8, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 9, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 8, 8, 7, 8, 9, 8, 9, 9, 8, 8, 8, 8, 8, 9, 9, 8, 9, 8, 9, 9, 7, 8, 9, 9, 8, 9, 8, 8, 8, 9, 9, 9, 8

Offset: 1

Author

Labos Elemer, Apr 13 2001

Keywords

• easy
• nonn

Comments

Indices of records in this sequence: 1, 2, 3, 5, 7, 13, 23, 33, 55, 116, 184, 384, 719, 1323, 2010, 4289, 6543, 13044, 25685, 45859, 92479, 175261, 298106, 636606, ... The records appear to be A000027. - Michael De Vlieger, Mar 27 2019.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A000040, A003434, A006093, A049108.

Programs

Mathematica

Array[-1 + Length@ NestWhileList[EulerPhi, Prime@ #, # > 1 &] &, 105] (* Michael De Vlieger, Mar 27 2019 *)

PARI

a(n) = my(t=0, p=prime(n)); while(p>1, t++; p=eulerphi(p)); t; \\ Michel Marcus, Mar 27 2019

Formula

a(n) = A003434(A000040(n)). [corrected by Michel Marcus, Mar 27 2019]

a(n) = A003434(A006093(n)) + 1. - Amiram Eldar, Nov 27 2024

Extensions

Name edited by Michel Marcus, Mar 27 2019