A286594 - OEIS

%I #18 Mar 02 2018 22:45:13

%S 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 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 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 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 Antti Karttunen, <a href="/A286594/b286594.txt">Table of n, a(n) for n = 1..10000</a>

%H Antti Karttunen, <a href="/A286594/a286594.txt">Scheme (Racket) program to compute this sequence</a>

%F a(n) = A285721(n, A000203(n)) = A285721(A000203(n), n).

%F a(n) = n - A300237(n). - _Antti Karttunen_, Mar 02 2018

%e For n = 1, sigma(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.

%e 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 For n = 6, sigma(6) = 12, gcd(12,6) = gcd(6,6), thus a(6) = 1.

%e 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 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 (Scheme) (define (A286594 n) (A285721bi n (A000203 n))) ;; Requires also code from A000203 and A285721.

%o (Python)

%o from sympy import divisor_sigma

%o def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))

%o def a(n): return A(n, divisor_sigma(n)) # _Indranil Ghosh_, May 22 2017

%o (PARI)

%o A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));

%o A286594(n) = A285721(n,sigma(n)); \\ _Antti Karttunen_, Mar 02 2018

%Y Cf. A000203, A009194, A285721.

%Y Cf. A000396 (positions of 1's).

%Y Cf. also A300227, A300228, A300234, A300237, A300238.

%K nonn

%O 1,2

%A _Antti Karttunen_, May 21 2017