A071575 Number of iterations of cototient(n) needed to reach 1 (cototient(n) = n-phi(n)).

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

Offset: 1

Author

Benoit Cloitre, May 31 2002

Keywords

• easy
• nonn

Examples

			cototient(6) = 4, cototient(4) = 2, cototient(2) = 1, hence a(6) = 3.
		

Links

• T. D. Noe, Table of n, a(n) for n=1..10000
• Paul Ellis, Jason Shi, Thotsaporn Aek Thanatipanonda, and Andrew Tu, Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT, arXiv:2309.01231 [math.NT], 2023. See p. 7.

Crossrefs

Cf. A032358, A051953, A076640.

Programs

Mathematica

cot[n_] := n - EulerPhi[n]; a[n_] := -1 + Length @ NestWhileList[cot, n, # > 1 &]; Array[a, 100] (* Amiram Eldar, May 19 2022 *)

PARI

for(n=1,150,s=n; t=0; while(s!=1,t++; s=s-eulerphi(s); if(s==1,print1(t,","); ); ))

Formula

a(n) = a(n-phi(n))+1, a(1) = 0.

a(n) = A076640(n)-1.

Extensions

Prepended a(1)=0 and changed offset. - T. D. Noe, Dec 03 2008