A385744 The number of iterations of the infinitary analog of the totient function A384247 that are required to reach from n to 1.

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

Offset: 1

Author

Amiram Eldar, Jul 08 2025

Keywords

• nonn
• easy

Comments

First differs from A049865 at n = 24.

Examples

			  n | a(n) | iterations
  --+------+----------------------
  2 |    1 | 2 -> 1
  3 |    2 | 3 -> 2 -> 1
  4 |    3 | 4 -> 3 -> 2 -> 1
  5 |    4 | 5 -> 4 -> 3 -> 2 -> 1
  6 |    2 | 6 -> 2 -> 1
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A384247, A385745, A385746, A385747.

Similar sequences: A003434, A049865, A225320, A333609.

Programs

Mathematica

f[p_, e_] := p^e*(1 - 1/p^(2^(IntegerExponent[e, 2]))); iphi[1] = 1; iphi[n_] := iphi[n] = Times @@ f @@@ FactorInteger[n];
a[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1; Array[a, 100]

PARI

iphi(n) = {my(f = factor(n)); n * prod(i = 1, #f~, (1 - 1/f[i, 1]^(1 << valuation(f[i, 2], 2))));}
a(n) = if(n ==  1, 0, 1 + a(iphi(n)));

Formula

a(n) = a(A384247(n)) + 1 for n >= 2.