|
%I #91 Mar 22 2024 12:33:47
%S 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 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 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 Number of elements merged by bottom-up merge sort.
%C 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 It appears that A045412 gives the indices of the terms which are greater than 1. - _Carl Joshua Quines_, Apr 07 2017
%D Donald E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Eq. (97).
%D Donald E. Knuth, The Art of Computer Programming, Addison-Wesley (2015) Vol. 4, Fascicle 6, Satisfiability, p. 80, Eq. (130).
%H N. J. A. Sloane, <a href="/A182105/b182105.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 Michael Luby Alistair, Alistair Sinclair, and David Zuckerman, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.156">Optimal speedup of Las Vegas algorithms</a>, Info. Processing Lett., 47 (1993), 173-180.
%H 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 The following two constructions are given by Knuth:
%F (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 (b) Set (u_1, v_1) = (1, 1), thereafter (u_{n+1}, v_{n+1}) = ( A ? B : C)
%F where
%F A = u_n & -u_n = v_n (where the AND refers to the binary expansions),
%F B = (u_n + 1, 1) (the result if A is true),
%F C = (u_n, 2v_n) (the result if A is false).
%F Then v_n = A182105, u_n = A046699 minus first term.
%F a(n) = 2^(A082850(n)-1). - _Laurent Orseau_, Jun 18 2019
%e Using construction (b), the initial values n, u_n, v_n are:
%e 1, 1, 1
%e 2, 2, 1
%e 3, 2, 2
%e 4, 3, 1
%e 5, 4, 1
%e 6, 4, 2
%e 7, 4, 4
%e 8, 5, 1
%e 9, 6, 1
%e 10, 6, 2
%e 11, 7, 1
%e 12, 8, 1
%e 13, 8, 2
%e 14, 8, 4
%e 15, 8, 8
%e 16, 9, 1
%e 17, 10, 1
%e 18, 10, 2
%e 19, 11, 1
%e 20, 12, 1
%e ...
%e From _Omar E. Pol_, Set 03 2013: (Start)
%e Illustration of initial terms (first 2^5-1 terms):
%e 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 ------------------------------------
%e . Diagram Triangle
%e ------------------------------------
%e . j / k: 1 2 3 4 5 / 1 2 3 4 5
%e ------------------------------------
%e . _ _ _ _ _
%e . 1 |_| | | | | 1;
%e . 2 |_ _| | | | 1,2;
%e . 3 |_| | | | 1;
%e . 4 |_ _ _| | | 1,2,4;
%e . 5 |_| | | | 1;
%e . 6 |_ _| | | 1,2;
%e . 7 |_| | | 1;
%e . 8 |_ _ _ _| | 1,2,4,8;
%e . 9 |_| | | | 1;
%e . 10 |_ _| | | 1,2;
%e . 11 |_| | | 1;
%e . 12 |_ _ _| | 1,2,4;
%e . 13 |_| | | 1;
%e . 14 |_ _| | 1,2;
%e . 15 |_| | 1;
%e . 16 |_ _ _ _ _| 1,2,4,8,16;
%e ...
%e (End)
%p A182105_list := proc(n) local L,m,k;
%p L := NULL;
%p for m from 1 to n do
%p for k from 0 to padic[ordp](m, 2) do
%p L := L,2^k od od;
%p L; end:
%p A182105_list(250);
%p # _Peter Luschny_, Aug 01 2012, based on _Charles R Greathouse IV_'s PARI program.
%t Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* _Michael De Vlieger_, Jan 22 2019 *)
%o (PARI) for(n=1,50,for(k=0,valuation(n,2),print1(2^k", "))) \\ _Charles R Greathouse IV_, Apr 12 2012
%Y Cf. A046699, A215020 (a version involving Fibonacci numbers).
%K nonn,easy
%O 1,3
%A _Dhruv Matani_, Apr 12 2012
%E Edited by _N. J. A. Sloane_, Aug 02 2012
|
