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

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.

Links

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

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.

Example

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

Prog

(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

Crossrefs

Cf. A072030, A285721.

Sequence in context: A082116 A079777 A224909 * A227536 A047773 A279416

Adjacent sequences: A377456 A377457 A377458 * A377460 A377461 A377462

Keyword

nonn,tabl,easy

Author

Thomas Anton, Jan 03 2025

Status

approved