|
|
A347735
|
|
Square array T(n, k), n, k > 0, read by antidiagonals; let b be the function that associates to any pair of integers (u, v) the Bézout coefficients (x, y) as produced by the extended Euclidean algorithm (u*x + v*y = gcd(u, v)); T(n, k) is the number of iterations of b when starting from (n, k) needed to obtain a unit vector.
|
|
1
|
|
|
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,8
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) = T(k, n).
T(n, n) = 1.
T(m*n, m*k) = T(n, k) for any m > 0.
|
|
EXAMPLE
|
Array T(n, k) begins:
n\k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---+---------------------------------------------------
1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2| 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2
3| 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1
4| 1 1 2 1 2 2 2 1 2 2 2 1 2 2 2
5| 1 2 2 2 1 2 3 3 2 1 2 3 3 2 1
6| 1 1 1 2 2 1 2 2 2 2 2 1 2 2 2
7| 1 2 2 2 3 2 1 2 3 3 3 3 2 1 2
8| 1 1 2 1 3 2 2 1 2 2 3 2 3 2 2
9| 1 2 1 2 2 2 3 2 1 2 3 2 3 3 2
10| 1 1 2 2 1 2 3 2 2 1 2 2 3 3 2
|
|
PROG
|
(PARI) T(n, k) = { for (v=0, oo, if (n^2+k^2<=1, return (v), [n, k]=gcdext(n, k)[1..2])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|