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

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

Author

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

Keywords

• nonn

Comments

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

Examples

			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.
		

References

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

Links

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

Crossrefs

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

Programs

Mathematica

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