A045412 -id:A045412 - cp's OEIS frontend

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

Dhruv Matani, Apr 12 2012

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

			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)

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

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.

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

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.

Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* Michael De Vlieger, Jan 22 2019 *)

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

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

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

A080468 a(n) = A080578(n)-2n.

Original entry on oeis.org

0, 1, 0, 1, 2, 1, 0, 1, 2, 1, 2, 3, 2, 1, 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 1, 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 1, 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4

Offset: 2

Benoit Cloitre, Oct 12 2003

nonn

Terms between 2^n and 2^(n+1) as n goes to infinity tend to the sequence : 0,1,2,1,2,3,2,1,2,3,2,3,4,3,2,1,2,3,2,3,4,3,2,3,4,3,4,5,4,3,2,1,....

Michael De Vlieger, Table of n, a(n) for n = 2..16384

Cf. A045412, A055938, A080578, A087805.

nn = 120; c[] := False; j = 1; c[1] = True; Reap[Do[Set[k, If[c[n], j + 1, j + 3]]; Set[{a[n], c[k], j}, {k - 2 n, True, k}]; Sow[a[n]], {n, 2, nn}] ][[-1, -1]] (* _Michael De Vlieger, Apr 29 2023 *)

a(2^n) = 0; Sum_{k=2^n..2^(n+1)} a(k) = n*2^(n-1) = A001787(n).

A118319 a(n) = (highest power of 2 dividing n)th integer among those positive integers not occurring in {a(1),a(2),a(3),...,a(n-1)}.

Original entry on oeis.org

1, 3, 2, 7, 4, 6, 5, 15, 8, 10, 9, 14, 11, 13, 12, 31, 16, 18, 17, 22, 19, 21, 20, 30, 23, 25, 24, 29, 26, 28, 27, 63, 32, 34, 33, 38, 35, 37, 36, 46, 39, 41, 40, 45, 42, 44, 43, 62, 47, 49, 48, 53, 50, 52, 51, 61, 54, 56, 55, 60, 57, 59, 58, 127, 64, 66, 65, 70, 67, 69, 68, 78

Offset: 1

Leroy Quet, Apr 23 2006

Sequence is a permutation of the positive integers. a(2n-1) is the smallest positive integer not occurring earlier in the sequence.

A101925 is the odd bisection, and it seems that A045412 is the sorted even bisection: a(2*n) = A045412(a(n)). - Andrey Zabolotskiy, Oct 09 2019

			4 is the highest power of 2 dividing 12. Those positive integers not occurring among the first 11 terms of the sequence form the sequence 11, 12, 13, 14, 16,... Now 14 is the 4th of these integers, so a(12) = 14.

Andrey Zabolotskiy, Table of n, a(n) for n = 1..8192
Index entries for sequences that are permutations of the natural numbers

Cf. A108918 (inverse permutation), A000120, A006519, A045412, A101925.

A118319 := proc(nmin) local a,anxt,i,n ; a := [1] ; while nops(a) < nmin do n := nops(a)+1 ; i := 2^A007814(n); anxt := 0 ; while i > 0 do anxt := anxt+1 ; while anxt in a do anxt := anxt+1 ; od ; i := i-1; od ; a := [op(a),anxt] ; od; a ; end: A118319(80) ; # R. J. Mathar, Sep 06 2007
a := n -> n + 2^padic[ordp](n, 2) - add(convert(n, base, 2)): seq(a(n), n = 1..72); # Peter Luschny, Mar 08 2025

a[1] := 1; a[n_] := a[n] =  Part[ Complement[ Range[2 n], Table[a[i], {i, n - 1}]],  2^IntegerExponent[n, 2]]; Array[a, 100] (* Birkas Gyorgy, Jul 09 2012 *)

PARI
```
a(n) = n + 1<Kevin Ryde, Mar 02 2025
```

a(2^m) = 2^(m+1) - 1; a(2^m+k) = a(k) + 2^m - 1 for 0 < k < 2^m. - Andrey Zabolotskiy, Oct 10 2019

a(n) = n + A006519(n) - A000120(n). - Kevin Ryde, Mar 08 2025

More terms from R. J. Mathar, Sep 06 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A080468 a(n) = A080578(n)-2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A118319 a(n) = (highest power of 2 dividing n)th integer among those positive integers not occurring in {a(1),a(2),a(3),...,a(n-1)}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions