A385744 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

First differs from A049865 at n = 24.

LINKS

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

FORMULA

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

EXAMPLE

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

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]

PROG

(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)));

CROSSREFS

Cf. A384247, A385745, A385746, A385747.

Similar sequences: A003434, A049865, A225320, A333609.

Sequence in context: A106653 A173524 A049865 * A070771 A274640 A245341

Adjacent sequences: A385741 A385742 A385743 * A385745 A385746 A385747

KEYWORD

nonn,easy

AUTHOR

Amiram Eldar, Jul 08 2025

STATUS

approved