A215020 -id:A215020 - cp's OEIS frontend

A082850 Let S(0) = {}, S(n) = {S(n-1), S(n-1), n}; sequence gives S(infinity).

1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 5, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 5, 6, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 4, 5, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1

Offset: 1

Benoit Cloitre, Apr 14 2003

Sequence counts up to successive values of A001511; i.e., apply the morphism k -> 1,2,...,k to A001511. If all 1's are removed from the sequence, the resulting sequence b has b(n) = a(n)+1. A101925 lists the positions of 1's in this sequence.

The geometric mean of this sequence approaches the Somos constant (A112302). - Jwalin Bhatt, Jan 30 2025

			S(1) = {1}, S(2) = {1,1,2}, S(3) = {1,1,2,1,1,2,3}, etc.

Alois P. Heinz, Table of n, a(n) for n = 1..65535

Cf. A082851 (partial sums).
Cf. A001511, A101925, A112302.
Cf. A215020.

Fold[Flatten[{#1, #1, #2}] &, {}, Range[5]] (* Birkas Gyorgy, Apr 13 2011 *)
Flatten[Table[Length@Last@Split@IntegerDigits[2 n, 2], {n, 20}] /. {n_ ->Range[n]}] (* Birkas Gyorgy, Apr 13 2011 *)

S = []; [S.extend(S + [n]) for n in range(1, 8)]
print(S) # Michael S. Branicky, Jul 02 2022

from itertools import count, islice
def A082850_gen(): # generator of terms
    S = []
    for n in count(1):
        yield from (m:=S+[n])
        S += m #
A082850_list = list(islice(A082850_gen(),20)) # Chai Wah Wu, Mar 06 2023

a(2^m - 1) = m.
If n = 2^m - 1 + k with 0 < k < 2^m, then a(n) = a(k). - Franklin T. Adams-Watters, Aug 16 2006
a(n) = log_2(A182105(n)) + 1. - Laurent Orseau, Jun 18 2019
a(n) = 1 + A215020(n). - Joerg Arndt, Mar 04 2025

A169683 The canonical skew-binary numbers.

Original entry on oeis.org

0, 1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1200, 2000, 10000, 10001, 10002, 10010, 10011, 10012, 10020, 10100, 10101, 10102, 10110

Offset: 0

N. J. A. Sloane, Apr 13 2010

Skew-binary is a positional system in which the n-th digit has weight 2^n-1, using digits 0, 1 and 2. In canonical form only the least significant nonzero digit is allowed to be 2.
The numbers can also be obtained as successive states of a counter: start at 0; increment by adding 1 to last digit, except if the current state ends with ...,x,2,0,...,0 with k trailing zeros, the next state is ...,x+1,0,0,...0 with k+1 trailing zeros.
Incrementing and decrementing numbers in this system can be done in O(1) since an increment will affect at most the two least significant nonzero digits and not carry through the entire number.
Popularized by the page numbers in the xkcd book.
Expansion of n in the q-system based on convergents to sqrt(2). [Fraenkel, 1982]. - N. J. A. Sloane, Aug 07 2018

			From _Joerg Arndt_, May 27 2016: (Start)
The first nonnegative skew-binary numbers (dots denote zeros) are
n :  [skew-binary]  position of leftmost change
00:  [ . . . . . ]  -
01:  [ . . . . 1 ]  0
02:  [ . . . . 2 ]  0
03:  [ . . . 1 . ]  1
04:  [ . . . 1 1 ]  0
05:  [ . . . 1 2 ]  0
06:  [ . . . 2 . ]  1
07:  [ . . 1 . . ]  2
08:  [ . . 1 . 1 ]  0
09:  [ . . 1 . 2 ]  0
10:  [ . . 1 1 . ]  1
11:  [ . . 1 1 1 ]  0
12:  [ . . 1 1 2 ]  0
13:  [ . . 1 2 . ]  1
14:  [ . . 2 . . ]  2
15:  [ . 1 . . . ]  3
16:  [ . 1 . . 1 ]  0
17:  [ . 1 . . 2 ]  0
18:  [ . 1 . 1 . ]  1
19:  [ . 1 . 1 1 ]  0
20:  [ . 1 . 1 2 ]  0
21:  [ . 1 . 2 . ]  1
22:  [ . 1 1 . . ]  2
23:  [ . 1 1 . 1 ]  0
24:  [ . 1 1 . 2 ]  0
25:  [ . 1 1 1 . ]  1
26:  [ . 1 1 1 1 ]  0
27:  [ . 1 1 1 2 ]  0
28:  [ . 1 1 2 . ]  1
29:  [ . 1 2 . . ]  2
30:  [ . 2 . . . ]  3
31:  [ 1 . . . . ]  4
32:  [ 1 . . . 1 ]  0
33:  [ 1 . . . 2 ]  0
...
The sequence of positions of the changes appears to be A215020.
(End)
From _Jianing Song_, May 16 2022: (Start)
a(2^1-1..2^2-2) = a(0..2^1-1) + 10^0 = [1, 2];
a(2^2-1..2^3-2) = a(0..2^2-1) + 10^1 = [10, 11, 12, 20];
a(2^3-1..2^4-2) = a(0..2^3-1) + 10^2 = [100, 101, 102, 110, 111, 112, 120, 200];
a(2^4-1..2^5-2) = a(0..2^4-1) + 10^3 = [1000, 1001, 1002, 1010, 1011, 1012, 1020, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1200, 2000];
... (End)

Chris Okasaki, Purely functional data structures, Cambridge University Press, Pittsburgh, 1999, pp. 76-77.
R. Munroe, xkcd, volume 0, Breadpig, San Francisco, 2009.

Martin Büttner, Table of n, a(n) for n = 0..10000 (terms up to a(110) from N. J. A. Sloane)
A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly, 89 (1982), 353-361. See Table 2.
E. W. Myers, An applicative random-access stack, Information Processing Letters 17.5, 1983, pages 241-248.
Wikipedia, Skew binary number system

f[0] = 0;
f[n_] := Module[{m = Floor@Log2[n + 1], d = n, pos}, Reap[While[m > 0, pos = 2^m - 1; Sow @ Floor[d/pos]; d = Mod[d, pos]; --m;]][[2, 1]] // FromDigits]
f /@ Range[0, 10000]

A169683(lim) = my(v=vector(1<Jianing Song, May 16 2022, gives a(0..2^lim-2)

a(0) = 0; for n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) for 0 <= i <= 2^n-1. - Jianing Song, May 16 2022

Definition edited by Martin Büttner, Jun 10 2015

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

Original entry on oeis.org

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

A215151 a(1) = 1; thereafter a(n+1) = 0 if bigomega(n) = bigomega(2^a(n)+n), otherwise a(n+1) = a(n)+1.

Original entry on oeis.org

1, 2, 3, 0, 1, 0, 1, 2, 0, 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 0, 1, 2, 3, 4, 0, 1, 2, 3, 0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5, 0, 1, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 1, 0, 1, 2, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 1

Offset: 1

Gerasimov Sergey, Aug 04 2012

			a(2)=2 (=a(1)+1) because A001222(1)=0 < A001222(2^1+1)=A001222(3)=1;
a(3)=3 (=a(2)+1) because A001222(2)=1 < A001222(2^2+2)=A001222(6)=2;
a(4)=0 (=0) because A001222(3)=1 = A001222(2^3+3)=A001222(11)=1;
a(5)=1 (=a(4)+1) because A001222(4)=2 > A001222(2^0+4)=A001222(5)=1;
a(6)=0 (=0) because A001222(5)=1 = A001222(2^1+5)=A001222(7)=1;
a(7)=1 (=a(6)+1) because A001222(6)=2 > A001222(2^0+6)=A001222(7)=1;
a(8)=2 (=a(7)+1) because A001222(7)=1 < A001222(2^1+7)=A001222(9)=2;
a(9)=0 (=0) because A001222(8)=3 = A001222(2^2+8)=A001222(12)=3.

Cf. A001222, A215020.

A215151 := proc(n)
        option remember;
        if n = 1 then
                1;
        elif  numtheory[bigomega](n-1) = numtheory[bigomega](2^procname(n-1)+n-1) then
                0 ;
        else
                procname(n-1)+1 ;
        end if;
end proc: # R. J. Mathar, Aug 07 2012

nxt[{n_,a_}]:={n+1,If[PrimeOmega[n]==PrimeOmega[2^a+n],0,a+1]}; Transpose[ NestList[nxt,{1,1},110]][[2]] (* Harvey P. Dale, Jun 17 2015 *)

A339451 Gray-code-like sequence in which, at each step, the least significant bit that has never been toggled from the previous value, is toggled.

Original entry on oeis.org

0, 1, 0, 2, 3, 2, 0, 4, 5, 4, 6, 7, 6, 4, 0, 8, 9, 8, 10, 11, 10, 8, 12, 13, 12, 14, 15, 14, 12, 8, 0, 16, 17, 16, 18, 19, 18, 16, 20, 21, 20, 22, 23, 22, 20, 16, 24, 25, 24, 26, 27, 26, 24, 28, 29, 28, 30, 31, 30, 28, 24, 16, 0, 32, 33, 32, 34, 35, 34, 32, 36

Offset: 0

Allan C. Wechsler, Dec 05 2020

Conjectured connections: the position of the bit that is toggled to derive a(n) from a(n-1) is A215020(n); the sequence of absolute differences of this sequence is A182105; there is some underlying connection to the "skew binary" counting system.

			For n = 18, a(n-1) = 8. That is the second 8 in the sequence. We cannot toggle the 1-bit, because that was already used to derive a(16) = 9 from a(15) = 8, so instead we toggle the 2-bit, yielding a(n) = 10.

Alois P. Heinz, Table of n, a(n) for n = 0..65535

Cf. A182105, A215020.

a:= proc() local b, a; b:= proc() 1/2 end; a:= proc(n)
      option remember; local h; if n=0 then 0 else h:=
      a(n-1); b(h):= 2*b(h); Bits[Xor](h, b(h)) fi end
    end():
seq(a(n), n=0..127);  # Alois P. Heinz, Dec 05 2020

a[m_] := Module[{b, a}, b[] = 1/2; a[n] := a[n] =
     Module[{h}, If[n == 0 ,  0 ,  h = a[n - 1];
     b[h] = 2*b[h]; BitXor[h, b[h]]]]; a[m]];
Table[a[n], {n, 0, 127}] (* Jean-François Alcover, May 15 2022, after Alois P. Heinz *)

cp's OEIS Frontend

A082850 Let S(0) = {}, S(n) = {S(n-1), S(n-1), n}; sequence gives S(infinity).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Python

Formula

A169683 The canonical skew-binary numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A215151 a(1) = 1; thereafter a(n+1) = 0 if bigomega(n) = bigomega(2^a(n)+n), otherwise a(n+1) = a(n)+1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

A339451 Gray-code-like sequence in which, at each step, the least significant bit that has never been toggled from the previous value, is toggled.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica