%I #7 Sep 15 2021 09:50:12
%S 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,
%T 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,
%U 2,2,3,2,2,3,2,2,2,1,1,1,2,2,2,2,1,2,2,2,2,1,1
%N 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.
%C For n, k > 0, b(n, k) = (A345415(n, k), A345416(n, k)).
%H Rémy Sigrist, <a href="/A347735/a347735.png">Colored representation of the array for n, k <= 1000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity">Bézout's identity</a>
%F T(n, k) = T(k, n).
%F T(n, n) = 1.
%F T(m*n, m*k) = T(n, k) for any m > 0.
%e Array T(n, k) begins:
%e n\k| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
%e ---+---------------------------------------------------
%e 1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
%e 2| 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2
%e 3| 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1
%e 4| 1 1 2 1 2 2 2 1 2 2 2 1 2 2 2
%e 5| 1 2 2 2 1 2 3 3 2 1 2 3 3 2 1
%e 6| 1 1 1 2 2 1 2 2 2 2 2 1 2 2 2
%e 7| 1 2 2 2 3 2 1 2 3 3 3 3 2 1 2
%e 8| 1 1 2 1 3 2 2 1 2 2 3 2 3 2 2
%e 9| 1 2 1 2 2 2 3 2 1 2 3 2 3 3 2
%e 10| 1 1 2 2 1 2 3 2 2 1 2 2 3 3 2
%o (PARI) T(n,k) = { for (v=0, oo, if (n^2+k^2<=1, return (v), [n,k]=gcdext(n,k)[1..2])) }
%Y Cf. A003989, A345415, A345416.
%K nonn,tabl
%O 1,8
%A _Rémy Sigrist_, Sep 11 2021
|