cp's OEIS Frontend

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.

%I A073408 #12 Dec 26 2017 13:42:28
%S A073408 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 A073408 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 A073408 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 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.
%H A073408 Antti Karttunen, <a href="/A073408/b073408.txt">Table of n, a(n) for n = 2..16385</a>
%F A073408 It seems that sum(k=1, n, a(k)) is asymptotic to C*n*log(n) with C < 1.
%e A073408 cophi(10) -> 6, cophi(6) -> 4, cophi(4) -> 2 and 2 divides 10. Hence 3 iterations are needed and a(10) = 3.
%t A073408 Table[Length@ NestWhileList[# - EulerPhi@ # &, n, Or[# == n, ! Divisible[n, #]] &, 1, 12] - 1, {n, 2, 106}] (* _Michael De Vlieger_, Dec 22 2017 *)
%o A073408 (PARI) a(n)=if(n<0,0,c=1; s=n; while(n%(s-eulerphi(s))>0,s=s-eulerphi(s); c++); c)
%Y A073408 Cf. A019294, A051953.
%K A073408 easy,nonn
%O A073408 2,5
%A A073408 _Benoit Cloitre_, Aug 23 2002