cp's OEIS Frontend

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

%I A325027 #104 Aug 07 2024 10:09:06
%S A325027 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,
%T A325027 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,
%U A325027 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
%N 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).
%C A325027 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.
%C A325027 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,
%C A325027 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.
%C A325027 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.
%C A325027 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.
%C A325027 Note: Neither example above is optimal; F(94,27,31) = 7 and F(86,33,17) = 5.
%D A325027 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.
%H A325027 Iliya Trub, <a href="/A325027/b325027.txt">Table of n, a(n) for n = 1..10000</a>
%H A325027 R. R. Sinha and M. Winslett, <a href="https://citeseerx.ist.psu.edu/pdf/a210b272ee79b74710972f947929f69ab1cd98e7">Multi-resolution bitmap indexes for scientific data</a>, ACM Transactions on Database Systems (TODS), vol.32, issue 3, 2007. P.1-39.
%H A325027 I. Trub, <a href="http://www.appliedinformatics.ru/general/upload/articles_preview/p53[3].pdf">Simulation of hierarchical bitmap-indices</a>. Prikladnaya informatika - Journal of Applied Informatics, 2018, vol.13, no. 4(76), pp.53-69 (in Russian).
%H A325027 I. Trub, <a href="http://www.appliedinformatics.ru/r/articles/article/index.php?article_id_4=2405">Advanced simulation based algorithm for search optimal size of bitmap index</a>, Prikladnaya informatika - Journal of Applied Informatics, 2019, vol. 14, no. 4(82), pp. 41-55 (in Russian).
%H A325027 Iliya Trub, <a href="/A325027/a325027_2.c.txt">C-program for sequence</a>
%H A325027 K. Wu, A. Shoshani, and K. Stockinger, <a href="https://crd-legacy.lbl.gov/~kewu/ps/LBNL-60891.html">Performance of multi-level and multi-component compressed bitmap indexes</a>, ACM Transactions on Database Systems, volume 35, issue 1, February 2010. P.1-52
%F A325027 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).
%F A325027 Some properties of T(n,k), for k > 1:
%F A325027 1) T(n,k) >= gcd(n,k).
%F A325027 2) If 2*k >= n, then T(n,k) <= 2*(n-k)-1.
%F A325027 3) If 2*k < n, then T(n,k) >= floor((n-k)/(k+1)).
%F A325027 4) If n > (k+1)^2 then T(n,k) = n.
%F A325027 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).
%F A325027 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.
%e A325027 Triangle begins:
%e A325027 n\k  0  1  2  3  4  5  6  7  8  9
%e A325027 ----------------------------------
%e A325027 1    1
%e A325027 2    2  1
%e A325027 3    3  1  1
%e A325027 4    4  2  2  1
%e A325027 5    5  5  2  1  1
%e A325027 6    6  6  2  3  2  1
%e A325027 7    7  7  2  3  2  1  1
%e A325027 8    8  8  2  4  4  2  2  1
%e A325027 9    9  9  3  3  4  3  3  1  1
%e A325027 10   10 10 10 3  5  5  2  2  2  1
%e A325027 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.
%o A325027 (C) // See link.
%o A325027 (PARI) roundhalfdown(x) = floor(ceil(2*x)/2);
%o A325027 roundhalfup(x) = ceil(floor(2*x)/2);
%o A325027 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];}
%o A325027 tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n,k), ", ")); print); \\ _Michel Marcus_, Apr 01 2019
%Y A325027 Cf. A325028.
%K A325027 nonn,easy,tabl
%O A325027 1,2
%A A325027 _Iliya Trub_, Mar 24 2019
%E A325027 Edited by _Charlie Neder_, Jun 18 2019