cp's OEIS Frontend

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.

%I A377459 #37 Jan 15 2025 09:01:55
%S A377459 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,
%T A377459 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,
%U A377459 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
%N 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.
%C A377459 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.
%F A377459 Uniquely determined by the following seven equations:
%F A377459 T(n,n) = 0,
%F A377459 T(n,2n) = 2,
%F A377459 T(2k,k) = 1,
%F A377459 T(n,n+k) = T(n,n-k)+3,
%F A377459 T(k+n,k) = T(k-n,k),
%F A377459 T(n,2n+k) = T(n,k)+3,
%F A377459 T(n+2k,k) = T(n,k)+3.
%e A377459 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,
%e A377459     5,2, 3, 1, 2, 1, 1
%e A377459          \-----------/  steps
%e A377459 The array begins:
%e A377459   n\k|  1  2  3  4  5  6   7   8  ...
%e A377459   ---+-------------------------------
%e A377459    1 |  0, 2, 3, 5, 6, 8,  9, 11, ...
%e A377459    2 |  1, 0, 4, 2, 4, 3,  7,  5, ...
%e A377459    3 |  3, 2, 0, 5, 6, 2,  6,  5, ...
%e A377459    4 |  4, 1, 4, 0, 7, 4,  7,  2, ...
%e A377459    5 |  6, 5, 3, 5, 0, 8,  6,  8, ...
%e A377459    6 |  7, 3, 1, 2, 7, 0, 10,  5, ...
%e A377459    7 |  9, 5, 6, 5, 6, 8,  0, 11, ...
%e A377459    8 | 10, 4, 7, 1, 4, 4, 10,  0, ...
%e A377459   ...
%o A377459 (Python)
%o A377459 def T(n,k):
%o A377459     old = n
%o A377459     new = k
%o A377459     steps = 0
%o A377459     while old != new:
%o A377459         old, new, steps = new, abs(new-old), steps+1
%o A377459     return steps
%Y A377459 Cf. A072030, A285721.
%K A377459 nonn,tabl,easy
%O A377459 1,3
%A A377459 _Thomas Anton_, Jan 03 2025