login
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
OFFSET
1,8
COMMENTS
For n, k > 0, b(n, k) = (A345415(n, k), A345416(n, k)).
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
nonn,tabl
AUTHOR
Rémy Sigrist, Sep 11 2021
STATUS
approved