login
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).
8
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, 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, 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
OFFSET
1,2
FORMULA
a(n) = A285721(n, A000203(n)) = A285721(A000203(n), n).
a(n) = n - A300237(n). - Antti Karttunen, Mar 02 2018
EXAMPLE
For n = 1, sigma(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.
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.
For n = 6, sigma(6) = 12, gcd(12,6) = gcd(6,6), thus a(6) = 1.
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.
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.
PROG
(Scheme) (define (A286594 n) (A285721bi n (A000203 n))) ;; Requires also code from A000203 and A285721.
(Python)
from sympy import divisor_sigma
def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
def a(n): return A(n, divisor_sigma(n)) # Indranil Ghosh, May 22 2017
(PARI)
A285721(n, k) = if(n==k, 0, 1 + A285721(abs(n-k), min(n, k)));
A286594(n) = A285721(n, sigma(n)); \\ Antti Karttunen, Mar 02 2018
CROSSREFS
Cf. A000396 (positions of 1's).
Sequence in context: A081806 A059806 A332425 * A241479 A100994 A375228
KEYWORD
nonn
AUTHOR
Antti Karttunen, May 21 2017
STATUS
approved