A377459 Square array T(n,k) read by ascending antidiagonals: number of steps for a certain Euclidean-style algorithm (see below) to find the GCD of n and k.

0, 1, 2, 3, 0, 3, 4, 2, 4, 5, 6, 1, 0, 2, 6, 7, 5, 4, 5, 4, 8, 9, 3, 3, 0, 6, 3, 9, 10, 5, 1, 5, 7, 2, 7, 11, 12, 4, 6, 2, 0, 4, 6, 5, 12, 13, 8, 7, 5, 7, 8, 7, 5, 7, 14, 15, 6, 3, 1, 6, 0, 6, 2, 3, 6, 15, 16, 8, 7, 8, 4, 8, 10, 8, 7, 8, 10, 17, 18, 7, 6, 5, 6, 4, 0, 5, 9, 4, 9, 8, 18

Offset: 1

Author

Thomas Anton, Jan 03 2025

Keywords

• nonn
• tabl
• easy

Comments

The algorithm begins with the list n,k. Each step appends to the list the absolute difference of the last two items on the list. The algorithm terminates when the last two items are equal. These will share the value of the GCD of n and k.

Examples

			For T(5,2), the list of successive absolute differences is as follows and reaches equal values (1,1) after T(5,2) = 5 steps,
    5,2, 3, 1, 2, 1, 1
         \-----------/  steps
The array begins:
  n\k|  1  2  3  4  5  6   7   8  ...
  ---+-------------------------------
   1 |  0, 2, 3, 5, 6, 8,  9, 11, ...
   2 |  1, 0, 4, 2, 4, 3,  7,  5, ...
   3 |  3, 2, 0, 5, 6, 2,  6,  5, ...
   4 |  4, 1, 4, 0, 7, 4,  7,  2, ...
   5 |  6, 5, 3, 5, 0, 8,  6,  8, ...
   6 |  7, 3, 1, 2, 7, 0, 10,  5, ...
   7 |  9, 5, 6, 5, 6, 8,  0, 11, ...
   8 | 10, 4, 7, 1, 4, 4, 10,  0, ...
  ...
		

Crossrefs

Cf. A072030, A285721.

Programs

Python

def T(n,k):
    old = n
    new = k
    steps = 0
    while old != new:
        old, new, steps = new, abs(new-old), steps+1
    return steps

Formula

Uniquely determined by the following seven equations:

T(n,n) = 0,

T(n,2n) = 2,

T(2k,k) = 1,

T(n,n+k) = T(n,n-k)+3,

T(k+n,k) = T(k-n,k),

T(n,2n+k) = T(n,k)+3,

T(n+2k,k) = T(n,k)+3.