A060610 Repeatedly apply Euler phi to the n-th prime; a(n) is the number of terms in the resulting iteration chain which are not powers of 2 (number of initial iterations until reaching the first power of 2).

0, 1, 1, 2, 2, 2, 1, 3, 3, 3, 2, 3, 2, 3, 4, 3, 4, 2, 3, 3, 3, 3, 3, 3, 2, 3, 2, 4, 4, 3, 4, 3, 2, 4, 4, 3, 3, 5, 4, 4, 4, 3, 4, 2, 4, 3, 3, 4, 4, 4, 4, 3, 2, 4, 1, 4, 4, 4, 4, 3, 5, 4, 3, 3, 3, 4, 3, 3, 5, 4, 3, 5, 3, 3, 5, 5, 3, 3, 3, 2, 4, 3, 4, 4, 4, 3, 3, 4, 4, 3, 5, 4, 6, 4, 4, 5, 5, 3, 4, 4, 4, 5, 4, 4, 4

Offset: 1

Author

Labos Elemer, Apr 13 2001

Keywords

• easy
• nonn

Examples

			n=100,p(100)=541, Phi-iteration chain is {541,540,144,48,16,8,4,2,1} with 9 terms. The first 4 terms (541,540,144,48) are not powers of 2, som a(100)=4.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000040, A000010, A049108, A049113, A049116, A049115, A003434.

Programs

Mathematica

Table[Count[FixedPointList[EulerPhi[#]&,Prime[n]],?(!IntegerQ[ Log[ 2,#]]&)],{n,110}] (* _Harvey P. Dale, Sep 18 2016 *)

Formula

a(n) = A049115(A000040(n)).

Extensions

Definition clarified by Harvey P. Dale, Sep 18 2016