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).

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

Author

Antti Karttunen, May 21 2017

Keywords

• nonn

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Antti Karttunen, Scheme (Racket) program to compute this sequence

Crossrefs

Cf. A000203, A009194, A285721.

Cf. A000396 (positions of 1's).

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

Programs

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

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

Scheme

(define (A286594 n) (A285721bi n (A000203 n))) ;; Requires also code from A000203 and A285721.

Formula

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

a(n) = n - A300237(n). - Antti Karttunen, Mar 02 2018