login
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, 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
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
Sequence in context: A032436 A360615 A280274 * A372572 A120454 A321648
KEYWORD
easy,nonn
AUTHOR
Benoit Cloitre, Aug 23 2002
STATUS
approved