OFFSET
1,2
COMMENTS
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.
REFERENCES
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.
LINKS
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
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) >= 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.
EXAMPLE
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.
PROG
(C) // See link.
(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))[1]; }
tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n, k), ", ")); print); \\ Michel Marcus, Apr 01 2019
CROSSREFS
KEYWORD
AUTHOR
Iliya Trub, Mar 24 2019
EXTENSIONS
Edited by Charlie Neder, Jun 18 2019
STATUS
approved