A071575 - OEIS

%I #24 Sep 07 2023 07:16:05

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

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

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

%N Number of iterations of cototient(n) needed to reach 1 (cototient(n) = n-phi(n)).

%H T. D. Noe, <a href="/A071575/b071575.txt">Table of n, a(n) for n=1..10000</a>

%H Paul Ellis, Jason Shi, Thotsaporn Aek Thanatipanonda, and Andrew Tu, <a href="https://arxiv.org/abs/2309.01231">Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT</a>, arXiv:2309.01231 [math.NT], 2023. See p. 7.

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

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

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

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

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

%Y Cf. A032358, A051953, A076640.

%K easy,nonn

%O 1,4

%A _Benoit Cloitre_, May 31 2002

%E Prepended a(1)=0 and changed offset. - _T. D. Noe_, Dec 03 2008