A285721 Square array read by antidiagonals: A(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k, read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

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

Offset

1,4

Links

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array

Formula

If n = k, then A(n,k) = 0, if n > k, then A(n,k) = 1 + A(n-k,k), otherwise [when n < k], A(n,k) = 1 + A(n,k-n).

Or alternatively, when n <> k, A(n,k) = 1 + A(abs(n-k),min(n,k)).

A(n,k) = A072030(n,k)-1.

As an one-dimensional sequence:

a(n) = 0 if A285722(n) = 0, otherwise a(n) = 1 + a(A285722(n)). [Here A285722 is also used as an one-dimensional sequence.]

Example

The top left 18 X 18 corner of the array:
   0, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12, 13, 14, 15, 16, 17
   1, 0, 2, 1, 3, 2, 4, 3, 5,  4,  6,  5,  7,  6,  8,  7,  9,  8
   2, 2, 0, 3, 3, 1, 4, 4, 2,  5,  5,  3,  6,  6,  4,  7,  7,  5
   3, 1, 3, 0, 4, 2, 4, 1, 5,  3,  5,  2,  6,  4,  6,  3,  7,  5
   4, 3, 3, 4, 0, 5, 4, 4, 5,  1,  6,  5,  5,  6,  2,  7,  6,  6
   5, 2, 1, 2, 5, 0, 6, 3, 2,  3,  6,  1,  7,  4,  3,  4,  7,  2
   6, 4, 4, 4, 4, 6, 0, 7, 5,  5,  5,  5,  7,  1,  8,  6,  6,  6
   7, 3, 4, 1, 4, 3, 7, 0, 8,  4,  5,  2,  5,  4,  8,  1,  9,  5
   8, 5, 2, 5, 5, 2, 5, 8, 0,  9,  6,  3,  6,  6,  3,  6,  9,  1
   9, 4, 5, 3, 1, 3, 5, 4, 9,  0, 10,  5,  6,  4,  2,  4,  6,  5
  10, 6, 5, 5, 6, 6, 5, 5, 6, 10,  0, 11,  7,  6,  6,  7,  7,  6
  11, 5, 3, 2, 5, 1, 5, 2, 3,  5, 11,  0, 12,  6,  4,  3,  6,  2
  12, 7, 6, 6, 5, 7, 7, 5, 6,  6,  7, 12,  0, 13,  8,  7,  7,  6
  13, 6, 6, 4, 6, 4, 1, 4, 6,  4,  6,  6, 13,  0, 14,  7,  7,  5
  14, 8, 4, 6, 2, 3, 8, 8, 3,  2,  6,  4,  8, 14,  0, 15,  9,  5
  15, 7, 7, 3, 7, 4, 6, 1, 6,  4,  7,  3,  7,  7, 15,  0, 16,  8
  16, 9, 7, 7, 6, 7, 6, 9, 9,  6,  7,  6,  7,  7,  9, 16,  0, 17
  17, 8, 5, 5, 6, 2, 6, 5, 1,  5,  6,  2,  6,  5,  5,  8, 17,  0

Prog

(Scheme)
(define (A285721 n) (A285721bi (A002260 n) (A004736 n)))
(define (A285721bi row col) (cond ((= row col) 0) ((> row col) (+ 1 (A285721bi (- row col) col))) (else (+ 1 (A285721bi row (- col row))))))
;; Alternatively:
(define (A285721bi row col) (if (= row col) 0 (+ 1 (A285721bi (abs (- row col)) (min col row)))))
;; Another implementation, as an one-dimensional sequence:
(definec (A285721 n) (if (zero? (A285722 n)) 0 (+ 1 (A285721 (A285722 n)))))
(Python)
def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
for n in range(1, 21): print([A(n - k + 1, k) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

Crossrefs

One less than A072030.

Row 2 & column 2: A028242 (but with starting offset 1).

Row 3 & column 3 (from zero onward) seems to be A226576.

Cf. A003989, A285722, A285732.

Compare also to arrays A049834, A113881, A219158.

Sequence in context: A305610 A220455 A208295 * A214292 A212184 A371571

Adjacent sequences: A285718 A285719 A285720 * A285722 A285723 A285724

Keyword

nonn,tabl

Author

Antti Karttunen, May 03 2017

Status

approved