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

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

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

Table of n, a(n) for n=1..120.

Iliya Trub, C program for sequence

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

Cf. A325027.

Sequence in context: A072699 A143589 A003651 * A073203 A073204 A322286

Adjacent sequences: A325025 A325026 A325027 * A325029 A325030 A325031

Keyword

nonn,easy,tabl

Author

Iliya Trub, Apr 05 2019

Status

approved