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

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.

Formula

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

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A032358, A051953, A076640.

Sequence in context: A025808 A144079 A326839 * A307908 A366737 A316436

Adjacent sequences: A071572 A071573 A071574 * A071576 A071577 A071578

Keyword

easy,nonn

Author

Benoit Cloitre, May 31 2002

Extensions

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

Status

approved