A351522 - OEIS

%I #7 Feb 19 2022 13:46:07

%S 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,

%T 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,

%U 5,6,6,7,7,6,6,5,3,1,1,3,4,5,6,7,6,7,6,5,4,3,1

%N 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 }.

%C 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).

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

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

%e Array T(n, k) begins:

%e   n\k|  0  1  2  3  4  5  6  7   8   9  10  11

%e   ---+----------------------------------------

%e     0|  0  1  1  1  1  1  1  1   1   1   1   1

%e     1|  1  2  3  3  3  3  3  3   3   3   3   3

%e     2|  1  3  3  4  4  5  4  5   4   5   4   5

%e     3|  1  3  4  3  5  5  5  5   6   5   6   6

%e     4|  1  3  4  5  4  6  6  6   6   7   6   7

%e     5|  1  3  5  5  6  5  7  7   8   8   8   8

%e     6|  1  3  4  5  6  7  6  8   8   8   8   8

%e     7|  1  3  5  5  6  7  8  7   9   9   9   9

%e     8|  1  3  4  6  6  8  8  9   8  10  10  11

%e     9|  1  3  5  5  7  8  8  9  10   9  11  11

%e    10|  1  3  4  6  6  8  8  9  10  11  10  12

%e    11|  1  3  5  6  7  8  8  9  11  11  12  11

%o (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)", "))) }

%o (Python)

%o from math import gcd

%o from functools import cache

%o @cache

%o def T(n, k):

%o     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))

%o def auptodiag(maxd):

%o     return [T(i, d-i) for d in range(maxd+1) for i in range(d+1)]

%o print(auptodiag(12)) # _Michael S. Branicky_, Feb 13 2022

%Y Cf. A049687.

%K nonn,tabl

%O 0,5

%A _Rémy Sigrist_, Feb 13 2022