login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182105 Number of elements merged by bottom-up merge sort. 6
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 (list; graph; refs; listen; history; text; internal format)
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

D. E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Equation (97).

Knuth, Donald E., Satisfiability,  Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, page 80, Eq. (130).

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

M. Luby, A. Sinclair and D. 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: A293438 A318622 A245195 * A023506 A232089 A140995

Adjacent sequences:  A182102 A182103 A182104 * A182106 A182107 A182108

KEYWORD

nonn,easy,changed

AUTHOR

Dhruv Matani, Apr 12 2012

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 12:55 EDT 2019. Contains 324352 sequences. (Running on oeis4.)