login
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
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,5
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).
FORMULA
T(n, k) = T(k, n).
T(n, k) <= A049687(n, k).
EXAMPLE
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
PROG
(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
CROSSREFS
Cf. A049687.
Sequence in context: A155582 A169946 A160832 * A157458 A174447 A174374
KEYWORD
nonn,tabl
AUTHOR
Rémy Sigrist, Feb 13 2022
STATUS
approved