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,8

Comments

For n, k > 0, b(n, k) = (A345415(n, k), A345416(n, k)).

Links

Table of n, a(n) for n=1..91.

Rémy Sigrist, Colored representation of the array for n, k <= 1000

Wikipedia, Bézout's identity

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

Cf. A003989, A345415, A345416.

Sequence in context: A274013 A172086 A339047 * A204014 A339184 A156839

Adjacent sequences: A347732 A347733 A347734 * A347736 A347737 A347738

Keyword

nonn,tabl

Author

Rémy Sigrist, Sep 11 2021

Status

approved