OFFSET
1,2
COMMENTS
The sequence {b(n,k)} is never below 1; Once it reaches a term 1, it continues to be 1 from that point.
Let b(n,k,i) = p(n,k,i)/q(n,k,i), where p(n,k,i) and q(n,k,i) are coprime positive integers, and d(n,k,i) = p(n,k,i) - q(n,k,i), f(n,k,i) = floor(i*b(n,k,i)). Hence b(n,k,i+1) = (i*p(n,k,i))/q(n,k,i)*f(n,k,i).
T(n,k) is well-defined. Proof (by contradiction): Suppose that for a given pair of (n,k), b(n,k,i) > 1 for every i, i.e. d(n,k,i) >= 1. Since b(n,k,i+1) = (i*b(n,k,i))/floor(i*b(n,k,i)) < 1 + 1/floor(i*b(n,k,i)) <= 1 + 1/i (1), we have i <= f(n,k,i) <= i+1 for i >= 2. We investigate the sequence {d(n,k)}. If f(n,k,i) = i, b(n,k,i+1) = (i*p(n,k,i))/q(n,k,i)*f(n,k,i) = p(n,k,i)/q(n,k,i), so d(n,k,i+1) = d(n,k,i); If f(n,k,i) = i+1, b(n,k,i+1) = (i*p(n,k,i))/((i+1)*q(n,k,i)), so d(n,k,i+1) <= i*p(n,k,i)-(i+1)*q(n,k,i) < p(n,k,i) - q(n,k,i) (from (1)) = d(n,k,i).
Therefore {d(n,k)} is a nonincreasing sequence of positive integers, so a number N exists such that for each i > N, d(n,k,i) = d(n,k,i+1), i.e. f(n,k,i) = i, thus i*b(n,k,i) < i+1. But b(n,k,i) > 1 remains constant for i > N, so a number M > N exists such that (M+1)/M <= b(n,k,M), a contradiction.
T(n,k) can be computed with recursion: Let N be the smallest number such that f(n,k,N) = N+1, i.e. b(n,k,N) >= (N+1)/N, N >= k/(n-k), so N = ceiling(k/(n-k)). Therefore b(n,k,i) = n/k for 1 <= i <= N, and b(n,k,N+1) = N*p(n,k,i)/q(n,k,i)*f(n,k,i) = (N*n)/((N+1)*k), and the remaining case is essentially the same as T(N*n, (N+1)*k) because the sequence {b(N*n, (N+1)*k)} remains constant for at least N terms.
LINKS
Yifan Xie, Rows n = 1..100 of triangle, flattened
FORMULA
T(n,n) = 1, T(n,n-1) = n.
T(n,1) = 2 for n >= 2, T(n,2) = n for odd numbers n >= 3 or 2 for even numbers n >= 4.
For n > k, T(n,k) = T(N*n, (N+1)*k) where N = ceiling(k/(n-k)).
T(n,k) < n^(2^floor(n mod k - 1)) <= n^(2^floor(n/2-1)).
EXAMPLE
The triangle begins:
n\k [1] [2] [3] [4] [5] [6] [7]
[1] 1;
[2] 2, 1;
[3] 2, 3, 1;
[4] 2, 2, 4, 1;
[5] 2, 5, 10, 5, 1;
[6] 2, 2, 2, 3, 6, 1;
[7] 2, 7, 7, 7, 21, 7, 1;
...
The sequence {b(5,3)} starts with b(5,3,1) = 5/3, b(5,3,2) = (5/3)/floor(5/3) = 5/3, b(5,3,3) = (2*5/3)/floor(2*5/3) = 10/9, b(5,3,4) = ... = b(5,3,9) = 10/9, and b(5,3,10) = (9*10/9)/floor(9*10/9) = 1. The smallest i for which b(5,3,i) = 1 is 10, so T(5,3) = 10.
PROG
(PARI) T(n, k)={if(n==k, return(1)); my(s=ceil(k/(n-k)), x=s*n, y=k*floor(s*n/k)); if(x==y, s+1, T(x, y))}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Yifan Xie, Feb 08 2025
STATUS
approved