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,3

Comments

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

It appears that A045412 gives the indices of the terms which are greater than 1. - Carl Joshua Quines, Apr 07 2017

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.

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).

Then v_n = A182105, u_n = A046699 minus first term.

a(n) = 2^(A082850(n)-1). - Laurent Orseau, Jun 18 2019

Example

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, Set 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)

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 *)

Prog

(PARI) for(n=1, 50, for(k=0, valuation(n, 2), print1(2^k", "))) \\ Charles R Greathouse IV, Apr 12 2012

Crossrefs

Cf. A046699, A215020 (a version involving Fibonacci numbers).

Sequence in context: A353785 A245195 A340191 * A023506 A232089 A141021

Adjacent sequences: A182102 A182103 A182104 * A182106 A182107 A182108

Keyword

nonn,easy

Author

Dhruv Matani, Apr 12 2012

Extensions

Edited by N. J. A. Sloane, Aug 02 2012

Status

approved