A182105 Number of elements merged by bottom-up merge sort.
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, 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, 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
Offset: 1
Examples
Using construction (b), the initial values n, u_n, v_n are: 1, 1, 1 2, 2, 1 3, 2, 2 4, 3, 1 5, 4, 1 6, 4, 2 7, 4, 4 8, 5, 1 9, 6, 1 10, 6, 2 11, 7, 1 12, 8, 1 13, 8, 2 14, 8, 4 15, 8, 8 16, 9, 1 17, 10, 1 18, 10, 2 19, 11, 1 20, 12, 1 ... From _Omar E. Pol_, Sep 03 2013: (Start) Illustration of initial terms (first 2^5-1 terms): 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): ------------------------------------ . Diagram Triangle ------------------------------------ . j / k: 1 2 3 4 5 / 1 2 3 4 5 ------------------------------------ . _ _ _ _ _ . 1 |_| | | | | 1; . 2 |_ _| | | | 1,2; . 3 |_| | | | 1; . 4 |_ _ _| | | 1,2,4; . 5 |_| | | | 1; . 6 |_ _| | | 1,2; . 7 |_| | | 1; . 8 |_ _ _ _| | 1,2,4,8; . 9 |_| | | | 1; . 10 |_ _| | | 1,2; . 11 |_| | | 1; . 12 |_ _ _| | 1,2,4; . 13 |_| | | 1; . 14 |_ _| | 1,2; . 15 |_| | 1; . 16 |_ _ _ _ _| 1,2,4,8,16; ... (End)
References
- Donald E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Eq. (97).
- Donald E. Knuth, The Art of Computer Programming, Addison-Wesley (2015) Vol. 4, Fascicle 6, Satisfiability, p. 80, Eq. (130).
Links
- N. J. A. Sloane, Table of n, a(n) for n = 1..10000
- Filip Bártek, Karel Chvalovský, and Martin Suda, Regularization in Spider-Style Strategy Discovery and Schedule Construction, arXiv:2403.12869 [cs.AI], 2024. See p. 5.
- Michael Luby Alistair, Alistair Sinclair, and David Zuckerman, Optimal speedup of Las Vegas algorithms, Info. Processing Lett., 47 (1993), 173-180.
- Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, Théophane Weber, Single-Agent Policy Tree Search With Guarantees, 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.
Programs
-
Maple
A182105_list := proc(n) local L,m,k; L := NULL; for m from 1 to n do for k from 0 to padic[ordp](m, 2) do L := L,2^k od od; L; end: A182105_list(250); # Peter Luschny, Aug 01 2012, based on Charles R Greathouse IV's PARI program.
-
Mathematica
Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* Michael De Vlieger, Jan 22 2019 *)
-
PARI
for(n=1,50,for(k=0,valuation(n,2),print1(2^k", "))) \\ Charles R Greathouse IV, Apr 12 2012
Formula
The following two constructions are given by Knuth:
(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.
(b) Set (u_1, v_1) = (1, 1), thereafter (u_{n+1}, v_{n+1}) = ( A ? B : C)
where
A = u_n & -u_n = v_n (where the AND refers to the binary expansions),
B = (u_n + 1, 1) (the result if A is true),
C = (u_n, 2v_n) (the result if A is false).
a(n) = 2^(A082850(n)-1). - Laurent Orseau, Jun 18 2019
Extensions
Edited by N. J. A. Sloane, Aug 02 2012
Comments