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).
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
Examples
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.
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
Crossrefs
Cf. A325028.
Programs
-
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
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.
Extensions
Edited by Charlie Neder, Jun 18 2019
Comments