A073408 - OEIS

%I #12 Dec 26 2017 13:42:28

%S 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,

%T 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,

%U 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

%N 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.

%H Antti Karttunen, <a href="/A073408/b073408.txt">Table of n, a(n) for n = 2..16385</a>

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

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

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

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

%Y Cf. A019294, A051953.

%K easy,nonn

%O 2,5

%A _Benoit Cloitre_, Aug 23 2002