cp's OEIS Frontend

A286594 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 = A000203(n).

%I A286594 #18 Mar 02 2018 22:45:13
%S A286594 0,2,3,4,5,1,7,8,6,5,11,4,13,5,4,16,17,7,19,11,12,6,23,3,10,6,15,1,29,
%T A286594 5,31,32,7,7,9,13,37,7,9,5,41,6,43,11,7,8,47,7,14,14,7,11,53,7,11,8,
%U A286594 15,9,59,6,61,9,12,64,10,8,67,11,8,20,71,9,73,10,13,9,23,9,79,17,42,11,83,4,11,11,8,23,89,5,7,9,16,12,8,6,97,17,9,16,101,11
%N A286594 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 = A000203(n).
%H A286594 Antti Karttunen, <a href="/A286594/b286594.txt">Table of n, a(n) for n = 1..10000</a>
%H A286594 Antti Karttunen, <a href="/A286594/a286594.txt">Scheme (Racket) program to compute this sequence</a>
%F A286594 a(n) = A285721(n, A000203(n)) = A285721(A000203(n), n).
%F A286594 a(n) = n - A300237(n). - _Antti Karttunen_, Mar 02 2018
%e A286594 For n = 1, sigma(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.
%e A286594 For n = 2, sigma(2) = 3, gcd(3,2) = gcd(2,1) = gcd(1,1), thus 2 steps were required to reach the termination condition, and a(2) = 2.
%e A286594 For n = 6, sigma(6) = 12, gcd(12,6) = gcd(6,6), thus a(6) = 1.
%e A286594 For n = 9, sigma(9) = 13, gcd(13,9) = gcd(9,4) = gcd(5,4) = gcd(4,1) = gcd(3,1) = gcd(2,1) = gcd(1,1), thus a(9) = 6.
%e A286594 Here the simple subtracting version of gcd-algorithm is used, where the new arguments will be the smaller argument and the smaller argument subtracted from the larger, and this is repeated until both are equal.
%o A286594 (Scheme) (define (A286594 n) (A285721bi n (A000203 n))) ;; Requires also code from A000203 and A285721.
%o A286594 (Python)
%o A286594 from sympy import divisor_sigma
%o A286594 def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
%o A286594 def a(n): return A(n, divisor_sigma(n)) # _Indranil Ghosh_, May 22 2017
%o A286594 (PARI)
%o A286594 A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
%o A286594 A286594(n) = A285721(n,sigma(n)); \\ _Antti Karttunen_, Mar 02 2018
%Y A286594 Cf. A000203, A009194, A285721.
%Y A286594 Cf. A000396 (positions of 1's).
%Y A286594 Cf. also A300227, A300228, A300234, A300237, A300238.
%K A286594 nonn
%O A286594 1,2
%A A286594 _Antti Karttunen_, May 21 2017