OFFSET
1,22
COMMENTS
For each pair (n,k), at least one of the conditions in the three formulas can be satisfied, so the problem of finding T(n,k) is reduced to finding T(n',k') with n'+k' < n+k and n',k' >= 1. Therefore T(n,k) can be uniquely determined with these formulas and the base cases T(2^t,2^t) = 0.
This also gives the inductive proof that T(n,k) >= 0.
LINKS
Yifan Xie, Table of n, a(n) for n = 1..5050 (first 100 antidiagonals)
Yifan Xie, Proof of the formulas
FORMULA
If 2^i < n <= n+k <= 2^(i+1) for some i, T(n,k) = T(n-2^i,k) + min(n-2^i,k).
If 2^i < k <= n+k <= 2^(i+1) for some i, T(n,k) = T(n,k-2^i) + min(n,k-2^i).
If n,k < 2^i <= n+k for some i, T(n,k) = T(2^i-n,2^i-k).
EXAMPLE
The array begins:
n\k [1] [2] [3] [4] [5] [6] [7]
[1] 0, 0, 1, 0, 1, 1, 2, ...
[2] 0, 0, 0, 0, 1, 2, 1, ...
[3] 1, 0, 0, 0, 2, 1, 1, ...
[4] 0, 0, 0, 0, 0, 0, 0, ...
[5] 1, 1, 2, 0, 0, 0, 1, ...
[6] 1, 2, 1, 0, 0, 0, 0, ...
[7] 2, 1, 1, 0, 1, 0, 0, ...
...
T(3,5) = S(8) - S(3) - S(5) - min(3,5) = 12 - 2 - 5 - 3 = 2.
PROG
(PARI)
s=vector(10000); s[1] = 0; for(n=2, 10000, s[n] = s[n-1] + hammingweight(n-1));
T(n, k) = s[n+k] - s[n] - s[k] - min(n, k);
CROSSREFS
KEYWORD
AUTHOR
Yifan Xie, Mar 17 2025
STATUS
approved
