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).
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, 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, 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
Offset: 1
Examples
Triangle:
n\k 0 1 2 3 4 5 6 7 8 9
----------------------------------
1 1
2 1 1
3 1 2 1
4 1 2 1 1
5 1 2 2 2 1
6 1 2 2 1 1 1
7 1 2 3 2 2 2 1
8 1 2 3 2 1 2 1 1
9 1 2 3 2 2 2 1 2 1
10 1 2 3 3 2 1 2 2 1 1
In particular, we have T(n,n-1) = 1, T(n,0) = 1 and T(n,1) = 2 for n > 2.
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.
References
- See "References" field for A325027.
Links
- Iliya Trub, C program for sequence
- See also "Links" field for A325027.
Crossrefs
Cf. A325027.
Programs
-
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];} tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n,k), ", ")); print);
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) <= min(k+1,n-k).
It follows from the definition, because F(n,k,n) = k + 1, F(n,k,1) = n - k.
2) If k^2 + k < n, then T(n,k) = k + 1.
3) If n <= k^2 + k and n mod k = 0, then T(n,k) = n/k - 1.
Comments