A003434 -id:A003434 - cp's OEIS frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2657, 5441, 10883, 17477, 40961, 65537, 140417, 295937, 557057, 1193537, 2384897, 4227137, 9548417, 17966357, 35946497, 71304257, 162174977, 305268737, 541073537, 1212153857, 2281701377

Offset: 2

Labos Elemer, Apr 13 2001

nonn

From 2nd to 12th term A007755 is the same as this sequence

			n=13: a(13)=2657 is the smallest prime which gives a chain of length 13, 2657 -> 2656 -> 1312 -> 640 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1, while the smallest number having this property is A007755(13) = 2329 -> 2176 -> 1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

T. D. Noe, Table of n, a(n) for n=2..1002
Project Euler, Problem 214: Totient chains.
T. D. Noe, Computing Numbers in Section I of the Totient Iteration

Cf. A000010, A049108 = A003434 + 1, A007755, A049117.

A007755 has the same initial terms but is a different sequence.

More terms from Jud McCranie, Apr 22 2001

Removed duplicate cross references, added link, reformulated example. - M. F. Hasler, Oct 25 2008

A092694 Product of iterated phi(n).

Original entry on oeis.org

1, 1, 2, 2, 8, 2, 12, 8, 12, 8, 80, 8, 96, 12, 64, 64, 1024, 12, 216, 64, 96, 80, 1760, 64, 1280, 96, 216, 96, 2688, 64, 1920, 1024, 1280, 1024, 1536, 96, 3456, 216, 1536, 1024, 40960, 96, 4032, 1280, 1536, 1760, 80960, 1024, 4032, 1280, 32768, 1536, 79872, 216

Offset: 1

T. D. Noe, Mar 04 2004

A logarithmic plot of this sequence shows an unusual banded structure.

			a(100) = 40960 because the iterations of phi (40, 16, 8, 4, 2, 1) have a product of 40960.

T. D. Noe, Table of n, a(n) for n=1..10000
T. D. Noe, Plot of A092694

Cf. A003434 (iterations of phi(n) needed to reach 1), A092693 (iterated phi sum).

Cf. A000010.

a092694 n = snd $ until ((== 1) . fst) f (a000010 n, 1) where
   f (x, p) = (a000010 x, p * x)
-- Reinhard Zumkeller, Jan 30 2014

nMax=100; a=Table[1, {nMax}]; Do[e=EulerPhi[n]; a[[n]]=e*a[[e]], {n, 2, nMax}]; a

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

a(1) = 1, a(n) = phi(n) * a(phi(n))

A173927 Smallest integer k such that the number of iterations of Carmichael lambda function (A002322) needed to reach 1 starting at k (k is counted) is n.

Original entry on oeis.org

1, 2, 3, 5, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 258280327, 688747547

Offset: 1

Michel Lagneau, Nov 26 2010

Smallest number k such that the trajectory of k under iteration of Carmichael lambda function contains exactly n distinct numbers (including k and the fixed point).
The first 13 terms are 1 or a prime. The next five terms are powers of 3. Then another prime. What explains this behavior? - T. D. Noe, Mar 23 2012
A185816(a(n)) = n - 1. - Reinhard Zumkeller, Sep 02 2014
If a(n) (n > 1) is either a prime or a power of 3, then a(n) is also the smallest integer k such that the number of iterations of Euler's totient function (A000010) needed to reach 1 starting at k (k is counted) is n. - Jianing Song, Jul 10 2019

			for n=5, a(5)=11 gives a chain of length 5 because the trajectory is 11 -> 10 -> 4 -> 2 -> 1.

Nick Harland, The number of iterates of the Carmichael lambda function required to reach 1, arXiv:1203.4791v1 [math.NT], Mar 21 2012.

Cf. A002322, A027763, A056637.

Cf. A185816 (number of iterations of Carmichael lambda function needed to reach 1), A003434 (number of iterations of Euler's totient function needed to reach 1).

import Data.List (elemIndex); import Data.Maybe (fromJust)
a173927 = (+ 1) . fromJust . (`elemIndex` map (+ 1) a185816_list)
-- Reinhard Zumkeller, Sep 02 2014

f[n_] := Length@ NestWhileList[ CarmichaelLambda, n, Unequal, 2] - 1; t = Table[0, {30}]; k = 1; While[k < 2100000001, a = f@ k; If[ t[[a]] == 0, t[[a]] = k; Print[a, " = ", k]]; k++] (* slightly modified by Robert G. Wilson v, Sep 01 2014 *)

a(20)-a(21) from Robert G. Wilson v, Sep 01 2014

A331921 Number of iterations of the map G -> Aut(G) on the cyclic group of order n needed to reach stability; or -1 if the iteration never stabilizes.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 2, 2, 3, 3, 4, 2, 2, 4, 5, 3, 3, 3, 4, 2, 3, 2, 3

Offset: 1

Sébastien Palcoux, Feb 01 2020

a(n) is the smallest m >= 0 such that Aut^{m+r}(Cn) is isomorphic to Aut^m(Cn) for some r > 0.
This sequence shares the first 7 terms with A003434 but not beyond, because Aut(Cn) has order phi(n) (see A000010) but need not be cyclic. It also shares the first 14 terms with A185816 (not beyond).
For n<32, G=Aut^{m+1}(Cn) is isomorphic to Aut^m(Cn) iff G is in {C1,S3,D8,D12,PGL(2,7)}. This is established by the GAP computation below.
Question: What is a(32)? (we just know that a(32)>=8)
Conjecture: a(n) != -1 for all n.
Question: Is there n such that the sequence Aut^m(Cn) reaches a loop of length>1?
From Jianing Song, Aug 13 2023 and edited on 24 Feb 2025: (Start)
It can be checked that a(n) != -1 for the following numbers:
 - 3^k and 2*3^k for all k >= 0;
 - 2*3^k+1 and 2*(2*3^k+1) for all k >= 0, where 2*3^k+1 is a prime;
 - p and 2*p for p = 13, 17, 23, 29, 31, 37, 47, 59, 67, 73, 89, 109, 173, 179, 197, 229, 347, 359, 457, 719, 1439, or 2879;
 - divisors of 16, 20, 30, 50, 168, 172, 196, 258, 264, 294, 456, 648, or 686.
The sequences of iterations are listed as follows (D_{2n} = dihedral group of order 2*n, S_n = symmetric group over set of size n, A_n = alternating group over set of size n):
 - C_{3^k}, C_{2*3^k} -> C_{2*3^(k-1)} -> ... -> C_2 -> C_1, k >= 1;
 - C_{2*3^k+1} or C_{2*(2*3^k+1)} -> C_{2*3^k} -> ... -> C_2 -> C_1, k >= 0, 2*3^k+1 is prime;
 - C_13 or C_26 -> C_8 or C_12 -> C_2 X C_2 -> S_3;
 - C_17, C_25, C_31, C_34, C_50, or C_62 -> C_15, C_16, C_20, or C_30 -> C_2 X C_4 -> D_8;
 - C_24 -> C_2 X C_2 X C_2 -> PSL(2,7) -> PGL(2,7);
 - C_47 or C_94 -> C_23 or C_46 -> C_11 or C_22 -> C_5 or C_10 -> C_4 -> C_2 -> C_1;
 - C_59 or C_118 -> C_29, C_37, C_43, C_49, C_58, C_74, C_86, or C_98 -> C_21, C_28, C_36, or C_42 -> C_2 X C_6 -> D_12;
 - C_67 or C_134 -> C_33, C_44, or C_66 -> C_2 X C_10 -> C_4 X S_3 -> C_2 X D_12 -> S_3 X S_4;
 - C_73 or C_146 -> C_56, C_72, or C_84 -> C_2 X C_2 X C_6 -> C_2 X PSL(2,7) -> PGL(2,7);
 - C_109 or C_218 -> C_57, C_76, C_108, or C_114 -> C_2 X C_18 -> C_6 X S_3 -> C_2 X D_12 -> S_3 X S_4;
 - C_168 -> C_2 X C_2 X C_2 X C_6 -> C_2 X A_8 -> S_8;
 - C_229 or C_458 -> C_152, C_216 or C_228 -> C_2 X C_2 X C_18 -> C_6 X PSL(2,7) -> C_2 X PGL(2,7);
 - C_264 -> C_2 X C_2 X C_2 X C_10 -> C_4 X A_8 -> C_2 X S_8;
 - C_324 -> C_2 X C_54 -> C_18 X S_3 -> C_6 X D_12 -> C_2 X D_12 X S_4 -> S_3 X S_4 X SmallGroup(96,227) -> S_3 X S_4 X SmallGroup(576,8654) -> S_3 X S_4 X SmallGroup(1152,157849);
 - C_347 or C_694 -> C_173, C_197, C_343, C_346, C_394 or C_686 -> C_129, C_147, C_172, C_196, C_258, or C_294 -> C_2 X C_42 -> C_6 X D_12 -> C_2 X D_12 X S_4 -> S_3 X S_4 X SmallGroup(96,227) -> S_3 X S_4 X SmallGroup(576,8654) -> S_3 X S_4 X SmallGroup(1152,157849);
 - C_457 or C_914 -> C_456 -> C_2 X C_2 X C_2 X C_18 -> C_6 X A_8 -> C_2 X S_8;
 - C_648 -> C_2 X C_2 X C_54 -> C_18 X PSL(2,7) -> C_6 X PGL(2,7) -> C_2 X C_2 X PGL(2,7) -> S_4 X PGL(2,7);
 - C_2879 or C_5758 -> C_1439 or C_2878 -> C_719 or C_1438 -> C_359 or C_718 -> C_179 or C_358 -> C_89 or C_178 -> C_88 or C_132 -> C_2 X C_2 X C_10 -> C_4 X PSL(2,7) -> C_2 X PGL(2,7).
The following two sequences are conjectured to be correct and to stabilize at the last term:
 - C_344, C_392, C_516, or C_588 -> C_2 X C_2 X C_42 -> C_2 X C_6 X PSL(2,7) - > D_12 X PGL(2,7) -> C_2 X D_12 X PGL(2,7) -> S_3 X PGL(2,7) X SmallGroup(96,227) -> S_3 X PGL(2,7) X SmallGroup(576,8654)? -> S_3 X PGL(2,7) X SmallGroup(1152,157849)?
 - C_1033 or C_2066 -> C_1032 or C_1176 -> C_2 X C_2 X C_2 X C_42 -> C_2 X C_6 X A_8 - > D_12 X S_8 -> C_2 X D_12 X S_8? -> S_3 X S_8 X SmallGroup(96,227)? -> S_3 X S_8 X SmallGroup(576,8654)? -> S_3 X S_8 X SmallGroup(1152,157849)? (End)

			Aut(C1)=C1 so a(1)=0.
Aut(C2)=C1 so a(2)=1.
Aut(C8)=C2xC2, Aut(C2xC2)=S3, Aut(S3)=S3, so a(8)=2 (whereas A003434(8)=3).
Aut(C15)=C2xC4, Aut(C2xC4)=D8, Aut(D8)=D8, so a(15)=2 (whereas A185816(15)=3).

A. P. Goucher, Iterated automorphism groups of finite groups, MathOverflow (2018).
G. Muller, Does Aut(Aut(...Aut(G)...)) stabilize?, MathOverflow (2009).
S. Palcoux, On the iterated automorphism groups of the cyclic groups, MathOverflow (2020).
Wikipedia, Multiplicative group of integers modulo n.

Cf. A000010, A003434, A185816, A117729, A179401.

gap> LoadPackage("sonata");
gap> L:=[];; SG:=[];; for n in [1..31] do a:=0; C:=CyclicGroup(n); A:=AutomorphismGroup(C); while Order(C)<>Order(A) or not IsIsomorphicGroup(A,C) do a:=a+1; C:=A; A:=AutomorphismGroup(A); od; Add(L,a); Add(SG,IdGroup(A)); od;
gap> L;
[ 0, 1, 2, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 2, 2, 3, 3, 4, 2, 2, 4, 5, 3, 3, 3, 4, 2, 3, 2, 3 ]
gap> SG;
[ [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 6, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 6, 1 ], [ 6, 1 ], [ 1, 1 ], [ 8, 3 ], [ 8, 3 ], [ 8, 3 ], [ 1, 1 ], [ 1, 1 ], [ 8, 3 ], [ 12, 4 ], [ 1, 1 ], [ 1, 1 ], [ 336, 208 ], [ 8, 3 ], [ 6, 1 ], [ 1, 1 ], [ 12, 4 ], [ 12, 4 ], [ 8, 3 ], [ 8, 3 ] ]
gap> Set(SG);
[ [ 1, 1 ], [ 6, 1 ], [ 8, 3 ], [ 12, 4 ], [ 336, 208 ] ]
# It is the list of IdGroup for C1, S3, D8, D12 and PGL(2,7).
# The above program works well for n<32. Beyond, it will work as long as there is no loop of length>1 and a(n) finite, which (for small n) is very likely (the opposite would be a breakthrough), otherwise it will just not end. Moreover, if Order(A) is too big then IdGroup(A) will not work, because the SmallGroup library of GAP is finite.

Escape clause added by Jianing Song, Aug 13 2023

A348213 a(n) is the number of iterations that n requires to reach a fixed point under the map x -> A348158(x).

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0

Offset: 1

Amiram Eldar, Oct 07 2021

nonn

a(n) first differs from 1-A000035(n) at n = 63.
The number of iterations is finite for all n since A348158(n) <= n.
The fixed points are terms of A326835, so a(n) = 0 if and only if n is a term of A326835.

			a(1) = 0 since 1 is in A326835.
a(2) = 1 since there is one iteration of the map x -> A348158(x) starting from 2: 2 -> 1.
a(64) = 2 since there are 2 iterations of the map x -> A348158(x) starting from 64: 64 -> 63 -> 57.

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

Cf. A000035, A003434, A326835, A348158.

f[n_] := Plus @@ DeleteDuplicates @ Map[EulerPhi, Divisors[n]]; a[n_] := -2 + Length @ FixedPointList[f, n]; Array[a, 100]

from sympy import totient, divisors
def A348213(n):
    c, k = 0, n
    m = sum(set(map(totient,divisors(k,generator=True))))
    while m != k:
        k = m
        m = sum(set(map(totient,divisors(k,generator=True))))
        c += 1
    return c # Chai Wah Wu, Nov 15 2021

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

Original entry on oeis.org

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

Amiram Eldar, Jul 08 2025

First differs from A049865 at n = 24.

			  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

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

Cf. A384247, A385745, A385746, A385747.

Similar sequences: A003434, A049865, A225320, A333609.

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]

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

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

A058811 Number of nodes at the n-th level of the Inverse-Totient-Tree (ITT) with the root at 1, and edges connecting number m to all numbers k such that phi(k) = m.

Original entry on oeis.org

1, 1, 3, 8, 17, 41, 92, 215, 487, 1126, 2583, 5981, 13698, 31647, 72678, 167474, 385021, 887133, 2041375, 4700526, 10817997, 24908164, 57334111, 131995229

Offset: 0

Labos Elemer, Jan 03 2001

Level 0 is the set {1}, and level k>=1 is the set of numbers t such that phi(t) is in the set of level k; a(n) is the cardinality of the set in level n. - Joerg Arndt, Jan 07 2015
The 3rd level is {5, 8, 10, 12, 7, 9, 14, 18} and a(3)=8. Generate invphi(5)={}, .., invphi(12)={13, 21, 26, 28, 36, 42}, ..., invphi(14)={}, .. The union of these inverses gives the 4th Floor ={15, 16, 20, 24, 30, 11, 22, 13, 21, 26, 28, 36, 42, 19, 27, 38, 54}, which has 17 terms. So a(4)=17. Each level-set may have entries either from A007617, A005278 (initial nodes of the tree) or from A000010 (invphi-continuable numbers).
Results of Shapiro show that largest number in the n-th level is 2*3^(n-1). The Mathematica code first computes A003434(k) for k <= 2*3^(n-1); then it gives the number of numbers k for which A003434(k) = n. - T. D. Noe, Mar 08 2004
Also, a(n) is the number of m such that phi^n(m) = 1, but phi^(n-1)(m) != 1. - Max Alekseyev, Jan 16 2025

			The 0th, 1st, 2nd and 3rd levels are {1}, {2}, {3, 4, 6}, {5, 7, 8, 9, 10, 12, 14, 18} with a(0) = 1, a(1) = 1, a(2) = 3, and a(3) = 8 elements, respectively.

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A007617, A005278.

Cf. A003434 (iterations of phi(n) needed to reach 1).

Table[ Length[ Select[ Range[ 1, 1050000 ], Equal[ flo[ # ], k ]& ] ], {k, 1, 20} ], where flo[ x_ ] := Length[ Delete[ FixedPointList[ EulerPhi, x ], -1 ] ]
nMax=16; kMax=2*3^(nMax-1); a=Table[0, {kMax}]; Do[e=EulerPhi[k]; a[[k]]=1+a[[e]], {k, 2, kMax}]; Table[Count[a, _?(#==n &)], {n, 0, nMax}]

lista(nn) = {my(v = [1]); print1(#v, ", "); for (n=1, nn, my(nv = []); for (i=1, #v, nv = Set(concat(nv, invphi(v[i])));); nv = setminus(nv, v); print1(#nv, ", "); v = nv;);} \\ Michel Marcus, Sep 02 2019

a(n) = Cardinality[Floor(n)], where Floor(0) = {1}, Floor(n+1) = Union_{i=1..a(n)} invphi(t(i, n)), where t(i, n) is the i-th integer in Floor(n), ordered by size or lexicographically.

a(13)-a(16) from T. D. Noe, Mar 08 2004
a(17)-a(23) from Sean A. Irvine, Aug 28 2022
Edited by Max Alekseyev, Jan 16 2025

A092878 Number of initial odd numbers in class n of the iterated phi function.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 16, 24, 33, 47, 60, 94, 122, 155, 187, 266, 354, 409, 550, 734, 955, 1186, 1472, 1864, 2404, 3026, 3712, 4675, 5939, 7260, 8826, 10970, 13529, 16572, 20104, 24943, 30391, 36790, 44416, 53925, 65216, 78658, 94300, 114196, 136821

Offset: 0

T. D. Noe, Mar 10 2004, Nov 30 2007, Nov 18 2008

nonn

Class n, for n>0, contains all numbers k such that n iterations of the Euler phi function applied to k yields 2; class 0 contains only the numbers 1 and 2. There is a conjecture that the smallest number in class n is always odd. This increasing sequence supports that conjecture. As shown by Shapiro, all the initial odd numbers in class n>0 are between 2^n and 2^(n+1).

			a(2) = 2 because the sequence of eight numbers 5,7,8,9,10,12,14,18 (which all take exactly 2 iterations of the phi function to produce 2) begins with 2 odd numbers.

R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed., New York, Springer-Verlag, 1994, B41.

T. D. Noe, Computing Numbers in Section I of the Totient Iteration
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A003434 (iterations of phi(n) needed to reach 1).
Cf. A058811 (number of numbers in class n).
Cf. A135833 (number of Section I primes).

nMax=23; nn=2^nMax; c=Table[0,{nn}]; Do[c[[n]]=1+c[[EulerPhi[n]]], {n,2,nn}]; Table[Length[Select[Flatten[Position[c,n]], #<=2^n && OddQ[ # ]&]], {n,0,nMax}]

A117729 Orders k of cyclic groups C_k such that the map "G -> Automorphism group of G" eventually reaches the trivial group when started at C_k.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 14, 18, 19, 22, 23, 27, 38, 46, 47, 54, 81, 94, 162, 163, 243, 326, 486, 487, 729, 974, 1458, 1459, 2187, 2918, 4374, 6561, 13122, 19683, 39366, 39367, 59049, 78734, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969

Offset: 1

N. J. A. Sloane, based on a communication from J. H. Conway, Apr 14 2006

nonn

If the map "G -> Automorphism group of G" eventually reaches the trivial group, then the initial group IS a cyclic group.
From Jianing Song, Oct 12 2019: (Start)
These are numbers k such that every step of the iteration results in a cyclic group, i.e., numbers k such that k, phi(k), phi(phi(k)), phi(phi(phi(k))), ... (or equivalently, k, A258615(k), A258615(A258615(k)), ...) are all in A033948, phi = A000010.
Number of iterations to reach the trivial group:
  k = 1: 0;
  k = 2: 1;
  k = 4: 2;
  k = 5, 10: 3;
  k = 11, 22: 4;
  k = 23, 46: 5;
  k = 47, 94: 6;
  k = 3^i, 2*3^i, i > 0: i+1;
  k = 2*3^i+1, 2*(2*3^i+1), i > 0, 2*3^i+1 is prime: i+2. (End)
From Peter Schorn, Apr 06 2021: (Start)
Since the values of a(n) have a simple formula it is easy to confirm by direct calculation for all cases that A003434(a(n)) = A185816(a(n)), i.e., the number of iterations to reach 1 via the Euler phi function is the same as the number of iterations to reach 1 via the Carmichael lambda function.
A computer search up to n = 10^8 also confirms the conjecture that if A003434(n) = A185816(n) then n is a term of A117729.
(End)

Cf. A033948, A000010, A258615, A331921, A003434, A185816.

t1:={ 4, 5, 10, 11, 22, 23, 46, 47, 94}; for i from 0 to 30 do t1:={op(t1),3^i, 2*3^i}; if isprime(2*3^i+1) then t1:={op(t1), 2*3^i+1, 2*(2*3^i+1)}; fi; od: convert(t1,list); sort(%);

ok(k)={my(f=1, t); while(f&&k>1, f=if(k%2, isprimepower(k), k==2 || k==4 || (isprimepower(k/2, &t) && t>2)); k=eulerphi(k)); f}
{ for(n=1, 10^9, if(ok(n), print1(n, ", "))) } \\ Andrew Howroyd, Oct 12 2019

Consists of the following numbers:
3^i and 2*3^i for all i >= 0;
if 2*3^i+1 is a prime, then also 2*3^i+1 and 2(2*3^i+1);
the exceptional entries 4, 5, 10, 11, 22, 23, 46, 47 and 94.

A347386 Number of iterations of A347385 (Dedekind psi function applied to the odd part of n) needed to reach a power of 2.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 2, 2, 2, 1, 2, 1, 2, 0, 3, 2, 3, 2, 1, 2, 2, 1, 3, 2, 3, 1, 3, 2, 1, 0, 2, 3, 2, 2, 4, 3, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 4, 3, 3, 1, 3, 3, 3, 2, 2, 1, 2, 0, 2, 2, 4, 3, 2, 2, 3, 2, 5, 4, 3, 3, 2, 2, 3, 2, 4, 2, 2, 1, 4, 3, 3, 2, 4, 3, 2, 2, 1, 2, 3, 1, 3, 2, 3, 3, 4, 3, 3, 2, 2

Offset: 1

Antti Karttunen, Aug 31 2021

nonn

Also, for n > 1, one less than the number of iterations of A347385 to reach 1.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A000265, A001615, A209229, A347385, A347387 (the exponent of the eventual power of 2 reached).

Cf. also A003434, A019269, A227944, A256757, A331410, A336361 for similar sequences.

f[p_, e_] := If[p == 2, 1, (p + 1)*p^(e - 1)]; psiOdd[1] = 1; psiOdd[n_] := Times @@ f @@@ FactorInteger[n]; a[n_] := -1 + Length @ NestWhileList[psiOdd, n, # != 2^IntegerExponent[#, 2] &]; Array[a, 100] (* Amiram Eldar, Aug 31 2021 *)

A347385(n) = if(1==n,n, my(f=factor(n>>valuation(n, 2))); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1)));
A347386(n) = if(!bitand(n, n-1), 0, 1+A347386(A347385(n)));

If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A001615(A000265(n))).

For all n >= 1, a(n) <= A331410(n).

cp's OEIS Frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A092694 Product of iterated phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

A173927 Smallest integer k such that the number of iterations of Carmichael lambda function (A002322) needed to reach 1 starting at k (k is counted) is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A331921 Number of iterations of the map G -> Aut(G) on the cyclic group of order n needed to reach stability; or -1 if the iteration never stabilizes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Extensions

A348213 a(n) is the number of iterations that n requires to reach a fixed point under the map x -> A348158(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A058811 Number of nodes at the n-th level of the Inverse-Totient-Tree (ITT) with the root at 1, and edges connecting number m to all numbers k such that phi(k) = m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI