cp's OEIS Frontend

A376613 The binary expansion of a(n) tracks where the merge operations occurs in a Tim sort algorithm applied to n blocks.

%I A376613 #32 Nov 02 2024 00:00:05
%S A376613 0,1,5,7,53,61,119,127,1973,2037,4029,4093,16247,16375,32639,32767,
%T A376613 1046453,1048501,2095093,2097141,8384445,8388541,16773117,16777213,
%U A376613 134201207,134217591,268419063,268435447,1073708927,1073741695,2147450879,2147483647,137437902773
%N A376613 The binary expansion of a(n) tracks where the merge operations occurs in a Tim sort algorithm applied to n blocks.
%C A376613 Initial blocks for the Tim sort merges are usually found by checking for existing ordered runs, or insertion sort on a small number of elements; then here a(n) is how the merges proceed for n blocks.
%C A376613 Each adjacent pair of blocks are merged, and if the number of blocks is odd then one block is left unchanged; then repeat that process until just 1 block remains.
%C A376613 Each merge performed is encoded as a 1 bit, and a block left unchanged is encoded as a 0 bit.
%C A376613 The total number of 1 bits in a(n) is n-1, since each merge reduces the number of blocks by 1. In other words, A000120(a(n)) = n - 1.
%C A376613 The bitsize of a(n) is A233272(n)-1.
%H A376613 Wikipedia, <a href="https://en.m.wikipedia.org/wiki/Timsort">Timsort</a>.
%H A376613 Geeks for Geeks, <a href="https://www.geeksforgeeks.org/timsort/">Timsort</a>.
%F A376613 a(2^k) = A077585(k).
%e A376613 For n = 10 a(10) = 2037 because:
%e A376613 Size | Block pair (l,m)(m,r) to merge | Left over block  | Encoding
%e A376613 -----+--------------------------------+------------------+-----------
%e A376613    1 | ((0, 0), (0, 1))               |                  | 1
%e A376613    1 | ((2, 2), (2, 3))               |                  | 11
%e A376613    1 | ((4, 4), (4, 5))               |                  | 111
%e A376613    1 | ((6, 6), (6, 7))               |                  | 1111
%e A376613    1 | ((8, 8), (8, 9))               |                  | 11111
%e A376613    2 | ((0, 1), (1, 3))               |                  | 111111
%e A376613    2 | ((4, 5), (5, 7))               |                  | 1111111
%e A376613    2 |                                | ((8, 9), (9, 9)) | 11111110
%e A376613    4 | ((0, 3), (3, 7))               |                  | 111111101
%e A376613    4 |                                | ((8, 9), (9, 9)) | 1111111010
%e A376613    8 | ((0, 7), (7, 9))               |                  | 11111110101
%e A376613 11111110101 in base 10 is 2037.
%e A376613 For n=10, the merges performed on 1,...,10 begin with pairs of "blocks" of length 1 each,
%e A376613   1  2  3  4  5  6  7  8  9  10
%e A376613   \--/  \--/  \--/  \--/  \---/
%e A376613    1     1     1     1      1    encoding
%e A376613   [1 2] [3 4] [5 6] [7 8] [9 10]
%e A376613   \---------/ \---------/
%e A376613        1           1        0    encoding
%e A376613 Similarly on the resulting 3 blocks
%e A376613   [1 2 3 4] [5 6 7 8] [9 10]
%e A376613   \-----------------/
%e A376613           1             0        encoding
%e A376613 Then a merge of the resulting 2 blocks to a single sorted block.
%e A376613   [1 2 3 4 5 6 7 8] [9 10]
%e A376613   \----------------------/
%e A376613             1                    encoding
%e A376613 These encodings are then a(10) = binary 11111 110 10 1 = 2037.
%o A376613 (Python)
%o A376613 def a(n):
%o A376613     if n == 1: return 0
%o A376613     s, t, n1 = 1, 0, (n - 1)
%o A376613     while s < n:
%o A376613         d = s << 1
%o A376613         for l in range(0, n, d):
%o A376613             m,r = min(l - 1 + s, n1), min(l - 1 + d, n1)
%o A376613             t = (t << 1) + int(m < r)
%o A376613         s = d
%o A376613     return t
%o A376613 print([a(n) for n in range (1,22)])
%Y A376613 Cf. A000079, A000120, A077585, A233272.
%K A376613 nonn,base
%O A376613 1,3
%A A376613 _Darío Clavijo_, Sep 29 2024