|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
|
|
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
|
(Python)
from sympy import divisor_sigma
def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
(PARI)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|