0,3

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

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

Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

T. D. Noe, Computing Numbers in Section I of the Totient Iteration [From T. D. Noe (noe(AT)sspectra.com), Nov 18 2008]

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.

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}]

Cf. A003434 (iterations of phi(n) needed to reach 1), A058811 (number of numbers in class n).

Cf. A135833 (number of Section I primes).

Sequence in context: A024783 A092855 A100111 this_sequence A126059 A126058 A050757

Adjacent sequences: A092875 A092876 A092877 this_sequence A092879 A092880 A092881

nonn

T. D. Noe (noe(AT)sspectra.com), Mar 10 2004, Nov 30 2007, Nov 18 2008