Iliya Trub - cp's OEIS frontend

User: Iliya Trub

Iliya Trub has authored 2 sequences.

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

Iliya Trub, Apr 05 2019

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.

			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.

See "References" field for A325027.

Iliya Trub, C program for sequence
See also "Links" field for A325027.

Cf. A325027.

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

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.

A325027 Triangle read by rows: T(n,k), 0 <= k < n, is the least m minimizing the number of intervals [a,a+1) or [ma,m(a+1)) that must be XORed together to form the interval [k,n).

Original entry on oeis.org

1, 2, 1, 3, 1, 1, 4, 2, 2, 1, 5, 5, 2, 1, 1, 6, 6, 2, 3, 2, 1, 7, 7, 2, 3, 2, 1, 1, 8, 8, 2, 4, 4, 2, 2, 1, 9, 9, 3, 3, 4, 3, 3, 1, 1, 10, 10, 10, 3, 5, 5, 2, 2, 2, 1, 11, 11, 11, 3, 4, 5, 6, 2, 2, 1, 1, 12, 12, 12, 3, 4, 6, 6, 4, 4, 3, 2, 1, 13, 13, 13, 3, 4, 6, 6, 7, 4, 3, 2, 1, 1

Offset: 1

Iliya Trub, Mar 24 2019

Searching an interval [k,n) of an array can be accomplished by splitting the array into large bins of a certain length, searching some number of large bins, and adding or removing individual items ("small bins") as required.
Let F(n,k,m) be the number of bins needed, using large bins of length m, to cover the interval [k,n). For example,
F(94,27,30) = 9, corresponding to seven small bins at {27,28,29,90,91,92,93} and two large bins [30,60) and [60,90). The large bins cover most of the interval and the remainder is covered by small bins.
F(86,33,30) = 9, corresponding to seven small bins at {30,31,32,86,87,88,89} and two large bins [30,60) and [60,90). In this case, the large bins cover the interval with remainder, and the small bins remove the excess.
T(n,k) is then the least m corresponding to a minimal value of F(n,k,m), which leads to optimal searching over that interval.
Note: Neither example above is optimal; F(94,27,31) = 7 and F(86,33,17) = 5.

			Triangle begins:
n\k  0  1  2  3  4  5  6  7  8  9
----------------------------------
1    1
2    2  1
3    3  1  1
4    4  2  2  1
5    5  5  2  1  1
6    6  6  2  3  2  1
7    7  7  2  3  2  1  1
8    8  8  2  4  4  2  2  1
9    9  9  3  3  4  3  3  1  1
10   10 10 10 3  5  5  2  2  2  1
In particular, we have T(n,n-1) = 1, T(n,0) = n, and T(n,k) <= n with equality for n > (k+1)^2.

E. Otoo, K. Wu, Accelerating Queries on Very Large Datasets, Scientific Data management. Challenges, Technology and Deployment (edited by Arie Shoshani, Doron Rotem). Chapman & Hall/CRC, 2010. P.183-234.

Iliya Trub, Table of n, a(n) for n = 1..10000
R. R. Sinha and M. Winslett, Multi-resolution bitmap indexes for scientific data, ACM Transactions on Database Systems (TODS), vol.32, issue 3, 2007. P.1-39.
I. Trub, Simulation of hierarchical bitmap-indices. Prikladnaya informatika - Journal of Applied Informatics, 2018, vol.13, no. 4(76), pp.53-69 (in Russian).
I. Trub, Advanced simulation based algorithm for search optimal size of bitmap index, Prikladnaya informatika - Journal of Applied Informatics, 2019, vol. 14, no. 4(82), pp. 41-55 (in Russian).
Iliya Trub, C-program for sequence
K. Wu, A. Shoshani, and K. Stockinger, Performance of multi-level and multi-component compressed bitmap indexes, ACM Transactions on Database Systems, volume 35, issue 1, February 2010. P.1-52

Cf. A325028.

C
```
// See link.
```

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))[1];}
tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n,k), ", ")); print); \\ Michel Marcus, Apr 01 2019

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) >= gcd(n,k).
2) If 2*k >= n, then T(n,k) <= 2*(n-k)-1.
3) If 2*k < n, then T(n,k) >= floor((n-k)/(k+1)).
4) If n > (k+1)^2 then T(n,k) = n.
5) If n satisfies k^2+k < n <= (n+1)^2 and there exists a nonnegative integer m < 1+sqrt(k+1) such that n=(k+m)*(k+2-m), then T(n,k) = k+m. For example, T(320,17) = 20 = 17+3, since 320 = 20*16 = (17+3)*(17-3+2).
6) T(k^2+k+1,k)=k. For example, T(7,2)=2 with F(7,2,2)=3, or T(13,3)=3 with F(13,3,3)=4.

Edited by Charlie Neder, Jun 18 2019

cp's OEIS Frontend

User: Iliya Trub

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula