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,3

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

References

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

Links

Table of n, a(n) for n=0..45.

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.

Example

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.

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

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

Sequence in context: A024783 A092855 A100111 * A126059 A126058 A233008

Adjacent sequences: A092875 A092876 A092877 * A092879 A092880 A092881

Keyword

nonn

Author

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

Status

approved