A073408 Let cophi_m(x) denotes the cototient function applied m times to x (cophi(x)=x-phi(x)). Sequence gives the minimum number of iterations m such that cophi_m(n) divides n.

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

Offset

2,5

Links

Antti Karttunen, Table of n, a(n) for n = 2..16385

Formula

It seems that sum(k=1, n, a(k)) is asymptotic to C*n*log(n) with C < 1.

Example

cophi(10) -> 6, cophi(6) -> 4, cophi(4) -> 2 and 2 divides 10. Hence 3 iterations are needed and a(10) = 3.

Mathematica

Table[Length@ NestWhileList[# - EulerPhi@ # &, n, Or[# == n, ! Divisible[n, #]] &, 1, 12] - 1, {n, 2, 106}] (* Michael De Vlieger, Dec 22 2017 *)

Prog

(PARI) a(n)=if(n<0, 0, c=1; s=n; while(n%(s-eulerphi(s))>0, s=s-eulerphi(s); c++); c)

Crossrefs

Cf. A019294, A051953.

Sequence in context: A032436 A360615 A280274 * A120454 A321648 A330755

Adjacent sequences: A073405 A073406 A073407 * A073409 A073410 A073411

Keyword

easy,nonn

Author

Benoit Cloitre, Aug 23 2002

Status

approved