cp's OEIS Frontend

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

%I A092878 #11 Jan 06 2015 03:49:27
%S A092878 1,1,2,3,5,7,13,16,24,33,47,60,94,122,155,187,266,354,409,550,734,955,
%T A092878 1186,1472,1864,2404,3026,3712,4675,5939,7260,8826,10970,13529,16572,
%U A092878 20104,24943,30391,36790,44416,53925,65216,78658,94300,114196,136821
%N A092878 Number of initial odd numbers in class n of the iterated phi function.
%C A092878 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).
%D A092878 R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed., New York, Springer-Verlag, 1994, B41.
%H A092878 T. D. Noe, <a href="http://www.sspectra.com/math/IteratedPhi2.pdf">Computing Numbers in Section I of the Totient Iteration</a>
%H A092878 Harold Shapiro, <a href="http://www.jstor.org/stable/2303988">An arithmetic function arising from the phi function</a>, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.
%e A092878 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.
%t A092878 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}]
%Y A092878 Cf. A003434 (iterations of phi(n) needed to reach 1).
%Y A092878 Cf. A058811 (number of numbers in class n).
%Y A092878 Cf. A135833 (number of Section I primes).
%K A092878 nonn
%O A092878 0,3
%A A092878 _T. D. Noe_, Mar 10 2004, Nov 30 2007, Nov 18 2008