A325028 - OEIS

%I #29 Jul 25 2019 21:22:11

%S 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 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 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 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 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 See "References" field for A325027.

%H Iliya Trub, <a href="/A325028/a325028.c.txt">C program for sequence</a>

%H See also "Links" field for A325027.

%F 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 Some properties of T(n,k), for k > 1:

%F 1) T(n,k) <= min(k+1,n-k).

%F It follows from the definition, because F(n,k,n) = k + 1, F(n,k,1) = n - k.

%F 2) If k^2 + k < n, then T(n,k) = k + 1.

%F 3) If n <= k^2 + k and n mod k = 0, then T(n,k) = n/k - 1.

%e Triangle:

%e n\k  0  1  2  3  4  5  6  7  8  9

%e ----------------------------------

%e 1    1

%e 2    1  1

%e 3    1  2  1

%e 4    1  2  1  1

%e 5    1  2  2  2  1

%e 6    1  2  2  1  1  1

%e 7    1  2  3  2  2  2  1

%e 8    1  2  3  2  1  2  1  1

%e 9    1  2  3  2  2  2  1  2  1

%e 10   1  2  3  3  2  1  2  2  1  1

%e In particular, we have T(n,n-1) = 1, T(n,0) = 1 and T(n,1) = 2 for n > 2.

%e 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 (PARI) roundhalfdown(x) = floor(ceil(2*x)/2);

%o roundhalfup(x) = ceil(floor(2*x)/2);

%o 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 tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n,k), ", ")); print);

%Y Cf. A325027.

%K nonn,easy,tabl

%O 1,5

%A _Iliya Trub_, Apr 05 2019