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, 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
Examples
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
Links
- Rémy Sigrist, Colored representation of the array for n, k <= 1000
- Wikipedia, Bézout's identity
Programs
-
PARI
T(n,k) = { for (v=0, oo, if (n^2+k^2<=1, return (v), [n,k]=gcdext(n,k)[1..2])) }
Formula
T(n, k) = T(k, n).
T(n, n) = 1.
T(m*n, m*k) = T(n, k) for any m > 0.
Comments