cp's OEIS Frontend

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

%I A325028 #29 Jul 25 2019 21:22:11
%S A325028 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,
%T A325028 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,
%U A325028 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
%N 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).
%C A325028 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.
%D A325028 See "References" field for A325027.
%H A325028 Iliya Trub, <a href="/A325028/a325028.c.txt">C program for sequence</a>
%H A325028 See also "Links" field for A325027.
%F A325028 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 A325028 Some properties of T(n,k), for k > 1:
%F A325028 1) T(n,k) <= min(k+1,n-k).
%F A325028 It follows from the definition, because F(n,k,n) = k + 1, F(n,k,1) = n - k.
%F A325028 2) If k^2 + k < n, then T(n,k) = k + 1.
%F A325028 3) If n <= k^2 + k and n mod k = 0, then T(n,k) = n/k - 1.
%e A325028 Triangle:
%e A325028 n\k  0  1  2  3  4  5  6  7  8  9
%e A325028 ----------------------------------
%e A325028 1    1
%e A325028 2    1  1
%e A325028 3    1  2  1
%e A325028 4    1  2  1  1
%e A325028 5    1  2  2  2  1
%e A325028 6    1  2  2  1  1  1
%e A325028 7    1  2  3  2  2  2  1
%e A325028 8    1  2  3  2  1  2  1  1
%e A325028 9    1  2  3  2  2  2  1  2  1
%e A325028 10   1  2  3  3  2  1  2  2  1  1
%e A325028 In particular, we have T(n,n-1) = 1, T(n,0) = 1 and T(n,1) = 2 for n > 2.
%e A325028 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.
%o A325028 (PARI) roundhalfdown(x) = floor(ceil(2*x)/2);
%o A325028 roundhalfup(x) = ceil(floor(2*x)/2);
%o A325028 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];}
%o A325028 tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n,k), ", ")); print);
%Y A325028 Cf. A325027.
%K A325028 nonn,easy,tabl
%O A325028 1,5
%A A325028 _Iliya Trub_, Apr 05 2019