|
| |
|
|
A325028
|
|
Triangle read by rows: T(n,k), 0 <= k < n, is the number of intervals [a,a+1) or [ma,m(a+1)) that must be XORed together to form the interval [k,n), where m = A325027(n,k).
|
|
2
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 2, 2, 1, 1, 2, 3, 2, 1, 2, 1, 1, 1, 2, 3, 2, 2, 2, 1, 2, 1, 1, 2, 3, 3, 2, 1, 2, 2, 1, 1, 1, 2, 3, 4, 3, 2, 2, 3, 2, 2, 1, 1, 2, 3, 3, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 3, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 4, 4, 3, 2, 1, 2, 3, 2, 2, 1, 1, 1, 2, 3, 4, 3, 2, 3, 2, 2, 2, 1, 2, 1, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
This sequence is closely related to A325027. The present sequence gives the optimal number of bins for a decomposition of the interval [k, n), whereas A325027 gives the size of the large bins in such a decomposition. A325027 was defined as the value m=T(n,k), where function F(n,k,m) reaches the minimum, and this sequence gives the value of this minimum.
|
|
|
REFERENCES
|
See "References" field for A325027.
|
|
|
LINKS
|
See also "Links" field for A325027.
|
|
|
FORMULA
|
If u = ceiling(n/m - 1/2) and v = floor(k/m + 1/2), then F(n,k,m) = u - v + abs(u*m-n) + abs(v*m-k).
Some properties of T(n,k), for k > 1:
1) T(n,k) <= min(k+1,n-k).
It follows from the definition, because F(n,k,n) = k + 1, F(n,k,1) = n - k.
2) If k^2 + k < n, then T(n,k) = k + 1.
3) If n <= k^2 + k and n mod k = 0, then T(n,k) = n/k - 1.
|
|
|
EXAMPLE
|
Triangle:
n\k 0 1 2 3 4 5 6 7 8 9
----------------------------------
1 1
2 1 1
3 1 2 1
4 1 2 1 1
5 1 2 2 2 1
6 1 2 2 1 1 1
7 1 2 3 2 2 2 1
8 1 2 3 2 1 2 1 1
9 1 2 3 2 2 2 1 2 1
10 1 2 3 3 2 1 2 2 1 1
In particular, we have T(n,n-1) = 1, T(n,0) = 1 and T(n,1) = 2 for n > 2.
It is interesting to note that this sequence grows quite slowly. Let us consider an auxiliary sequence {T_grow(m)}, where T_grow(m) is the first n such that row n contains an m. The first terms of T_grow are 1, 3, 7, 11, 19, 27, 38, 51, 67, 75, 93, 114, 137, 147, 173, 212, 243, 276, 297, 327, 371, 403, 445.
|
|
|
PROG
|
(PARI) roundhalfdown(x) = floor(ceil(2*x)/2);
roundhalfup(x) = ceil(floor(2*x)/2);
T(n, k) = {v = vector(n, z, roundhalfdown(n/z) - roundhalfup(k/z) + abs(z*roundhalfup(k/z)-k) + abs(z*roundhalfdown(n/z)-n)); (vecsort(v))[1]; }
tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n, k), ", ")); print);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
