A351522 Square array T(n, k) read by antidiagonals, n, k >= 0; T(n, k) is the number of distinct values in the set { T(i, j) with 0 <= i <= n and 0 <= j <= k and gcd(n-i, k-j) = 1 }.

0, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 4, 4, 3, 1, 1, 3, 4, 3, 4, 3, 1, 1, 3, 5, 5, 5, 5, 3, 1, 1, 3, 4, 5, 4, 5, 4, 3, 1, 1, 3, 5, 5, 6, 6, 5, 5, 3, 1, 1, 3, 4, 5, 6, 5, 6, 5, 4, 3, 1, 1, 3, 5, 6, 6, 7, 7, 6, 6, 5, 3, 1, 1, 3, 4, 5, 6, 7, 6, 7, 6, 5, 4, 3, 1

Offset: 0

Author

Rémy Sigrist, Feb 13 2022

Keywords

• nonn
• tabl

Comments

In other words, T(n, k) gives the number of distinct values in the rectangle with opposite corners (0, 0) and (n, k) visible from (n, k).

Examples

			Array T(n, k) begins:
  n\k|  0  1  2  3  4  5  6  7   8   9  10  11
  ---+----------------------------------------
    0|  0  1  1  1  1  1  1  1   1   1   1   1
    1|  1  2  3  3  3  3  3  3   3   3   3   3
    2|  1  3  3  4  4  5  4  5   4   5   4   5
    3|  1  3  4  3  5  5  5  5   6   5   6   6
    4|  1  3  4  5  4  6  6  6   6   7   6   7
    5|  1  3  5  5  6  5  7  7   8   8   8   8
    6|  1  3  4  5  6  7  6  8   8   8   8   8
    7|  1  3  5  5  6  7  8  7   9   9   9   9
    8|  1  3  4  6  6  8  8  9   8  10  10  11
    9|  1  3  5  5  7  8  8  9  10   9  11  11
   10|  1  3  4  6  6  8  8  9  10  11  10  12
   11|  1  3  5  6  7  8  8  9  11  11  12  11
		

Crossrefs

Cf. A049687.

Programs

PARI

{ T = matrix(M=13,M); for (d=1, #T, for (k=1, d, n=d+1-k; w=0; for (i=1, n, for (j=1, k, if (gcd(n-i, k-j)==1, w=bitor(w, 2^T[i,j])))); print1 (T[n,k] = hammingweight(w)", "))) }

Python

from math import gcd
from functools import cache
@cache
def T(n, k):
    return len(set(T(i, j) for i in range(n+1) for j in range(k+1) if gcd(n-i, k-j) == 1))
def auptodiag(maxd):
    return [T(i, d-i) for d in range(maxd+1) for i in range(d+1)]
print(auptodiag(12)) # Michael S. Branicky, Feb 13 2022

Formula

T(n, k) = T(k, n).

T(n, k) <= A049687(n, k).