cp's OEIS Frontend

A182105 Number of elements merged by bottom-up merge sort.

%I A182105 #97 Aug 02 2025 06:51:25
%S A182105 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,1,1,2,
%T A182105 1,1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,32,1,1,2,1,
%U A182105 1,2,4,1,1,2,1,1,2,4,8,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,16,1,1,2,1,1,2,4,1,1,2,1,1,2,4,8
%N A182105 Number of elements merged by bottom-up merge sort.
%C A182105 Also triangle read by rows in which row j lists the first A001511(j) powers of 2, j >= 1, hence records give A000079. Right border gives A006519. Row sums give A038712. The equivalent sequence for partitions is A211009. See example. - _Omar E. Pol_, Sep 03 2013
%C A182105 It appears that A045412 gives the indices of the terms which are greater than 1. - _Carl Joshua Quines_, Apr 07 2017
%D A182105 Donald E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Eq. (97).
%D A182105 Donald E. Knuth, The Art of Computer Programming, Addison-Wesley (2015) Vol. 4, Fascicle 6, Satisfiability, p. 80, Eq. (130).
%H A182105 N. J. A. Sloane, <a href="/A182105/b182105.txt">Table of n, a(n) for n = 1..10000</a>
%H A182105 Filip Bártek, Karel Chvalovský, and Martin Suda, <a href="https://arxiv.org/abs/2403.12869">Regularization in Spider-Style Strategy Discovery and Schedule Construction</a>, arXiv:2403.12869 [cs.AI], 2024. See p. 5.
%H A182105 Michael Luby Alistair, Alistair Sinclair, and David Zuckerman, <a href="https://citeseerx.ist.psu.edu/pdf/3240392cf2a4405031257383e3202cb020749449">Optimal speedup of Las Vegas algorithms</a>, Info. Processing Lett., 47 (1993), 173-180.
%H A182105 Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, Théophane Weber, <a href="https://arxiv.org/abs/1811.10928">Single-Agent Policy Tree Search With Guarantees</a>, arXiv:1811.10928 [cs.AI], 2018, also in Advances in Neural Information Processing Systems, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.
%F A182105 The following two constructions are given by Knuth:
%F A182105 (a) a(1) = 1; thereafter a(n+1) = 2a(n) if a(n) has already occurred an even number of times, otherwise a(n+1) = 1.
%F A182105 (b) Set (u_1, v_1) = (1, 1), thereafter (u_{n+1}, v_{n+1}) = ( A ? B : C)
%F A182105 where
%F A182105 A = u_n & -u_n = v_n (where the AND refers to the binary expansions),
%F A182105 B = (u_n + 1, 1) (the result if A is true),
%F A182105 C = (u_n, 2v_n) (the result if A is false).
%F A182105 Then v_n = A182105, u_n = A046699 minus first term.
%F A182105 a(n) = 2^(A082850(n)-1). - _Laurent Orseau_, Jun 18 2019
%e A182105 Using construction (b), the initial values n, u_n, v_n are:
%e A182105   1, 1, 1
%e A182105   2, 2, 1
%e A182105   3, 2, 2
%e A182105   4, 3, 1
%e A182105   5, 4, 1
%e A182105   6, 4, 2
%e A182105   7, 4, 4
%e A182105   8, 5, 1
%e A182105   9, 6, 1
%e A182105   10, 6, 2
%e A182105   11, 7, 1
%e A182105   12, 8, 1
%e A182105   13, 8, 2
%e A182105   14, 8, 4
%e A182105   15, 8, 8
%e A182105   16, 9, 1
%e A182105   17, 10, 1
%e A182105   18, 10, 2
%e A182105   19, 11, 1
%e A182105   20, 12, 1
%e A182105   ...
%e A182105 From _Omar E. Pol_, Sep 03 2013: (Start)
%e A182105 Illustration of initial terms (first 2^5-1 terms):
%e A182105 Written as an irregular triangle: T(j,k) is also the length of the k-th column in the j-th region of the diagram, as shown below. Note that the j-th row of the diagram is equivalent to the j-th composition (in colexicographic order) of 5 (cf. A228525):
%e A182105 ------------------------------------
%e A182105 .          Diagram      Triangle
%e A182105 ------------------------------------
%e A182105 .  j / k: 1 2 3 4 5  /  1 2 3 4 5
%e A182105 ------------------------------------
%e A182105 .         _ _ _ _ _
%e A182105 .  1     |_| | | | |    1;
%e A182105 .  2     |_ _| | | |    1,2;
%e A182105 .  3     |_|   | | |    1;
%e A182105 .  4     |_ _ _| | |    1,2,4;
%e A182105 .  5     |_| |   | |    1;
%e A182105 .  6     |_ _|   | |    1,2;
%e A182105 .  7     |_|     | |    1;
%e A182105 .  8     |_ _ _ _| |    1,2,4,8;
%e A182105 .  9     |_| | |   |    1;
%e A182105 . 10     |_ _| |   |    1,2;
%e A182105 . 11     |_|   |   |    1;
%e A182105 . 12     |_ _ _|   |    1,2,4;
%e A182105 . 13     |_| |     |    1;
%e A182105 . 14     |_ _|     |    1,2;
%e A182105 . 15     |_|       |    1;
%e A182105 . 16     |_ _ _ _ _|    1,2,4,8,16;
%e A182105 ...
%e A182105 (End)
%p A182105 A182105_list := proc(n) local L,m,k;
%p A182105 L := NULL;
%p A182105 for m from 1 to n do
%p A182105 for k from 0 to padic[ordp](m, 2) do
%p A182105 L := L,2^k od od;
%p A182105 L; end:
%p A182105 A182105_list(250);
%p A182105 # _Peter Luschny_, Aug 01 2012, based on _Charles R Greathouse IV_'s PARI program.
%t A182105 Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* _Michael De Vlieger_, Jan 22 2019 *)
%o A182105 (PARI) for(n=1,50,for(k=0,valuation(n,2),print1(2^k", "))) \\ _Charles R Greathouse IV_, Apr 12 2012
%Y A182105 Cf. A046699, A215020 (a version involving Fibonacci numbers).
%K A182105 nonn,easy
%O A182105 1,3
%A A182105 _Dhruv Matani_, Apr 12 2012
%E A182105 Edited by _N. J. A. Sloane_, Aug 02 2012