0,4

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

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 (Jan., 1943), 18-30.

a(3) = 2 because the sequence of eight numbers 5,7,8,9,10,12,14,18 (which all take exactly 3 iterations of the phi function to produce 1) 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