cp's OEIS Frontend

A300234 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = phi(n).

%I A300234 #8 Mar 02 2018 22:44:35
%S A300234 0,1,2,1,4,2,6,1,2,3,10,2,12,4,8,1,16,2,18,3,4,6,22,2,4,7,2,4,28,6,30,
%T A300234 1,9,9,9,2,36,10,5,3,40,4,42,6,8,12,46,2,6,3,10,7,52,2,5,4,6,15,58,6,
%U A300234 60,16,4,1,10,8,66,9,11,13,70,2,72,19,8,10,13,6,78,3,2,21,82,4,24,22,12,6,88,6,11,12,8,24,13,2,96,4,9,3,100,10,102,7,9
%N A300234 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = phi(n).
%H A300234 Antti Karttunen, <a href="/A300234/b300234.txt">Table of n, a(n) for n = 1..65537</a>
%H A300234 Antti Karttunen, <a href="/A286594/a286594.txt">Scheme (Racket) program to compute this sequence</a>
%F A300234 a(n) = A285721(n,A000010(n)).
%F A300234 a(n) = n - A300238(n).
%e A300234 For n = 1, phi(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.
%e A300234 For n = 2, eulerphi(2) = 1, gcd(2,1) = gcd(1,1), thus 1 step were required to reach the termination condition, and a(2) = 1.
%e A300234 For n = 5, eulerphi(5) = 4, gcd(5,4) = gcd(4,1) = gcd(3,1) = gcd(2,1) = gcd(1,1), four steps required, thus a(5) = 4.
%e A300234 For n = 6, eulerphi(6) = 2, gcd(6,2) = gcd(4,2) = gcd(2,2), two steps required, thus a(6) = 2.
%e A300234 Here a simple subtracting version of gcd-algorithm is used, where the new versions of two arguments will be the smaller argument and the smaller argument subtracted from the larger, and this is repeated until both are equal.
%o A300234 (PARI)
%o A300234 A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
%o A300234 A300234(n) = A285721(n,eulerphi(n));
%Y A300234 Cf. A000010, A285721.
%Y A300234 Cf. also A286594, A300227, A300228, A300237, A300238.
%K A300234 nonn
%O A300234 1,3
%A A300234 _Antti Karttunen_, Mar 02 2018