A108918 -id:A108918 - cp's OEIS frontend

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1

Offset: 0

Vladeta Jovovic, Jan 25 2003

Differences of the Meta-Fibonacci sequence for s=0. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
Fixed point of morphism 0-->0, 1-->110 - Joerg Arndt, Jun 07 2007
A006697(k) gives number of distinct subwords of length k, conjectured to be equal to A094913(k)+1. - M. F. Hasler, Dec 19 2007
Characteristic function for the range of A005187: a(A055938(n))=0; a(A005187(n))=1; if a(m)=1 then either a(m-1)=1 or a(m+1)=1. - Reinhard Zumkeller, Mar 18 2009
The number of zeros between successive pairs of ones in this sequence is A007814. - Franklin T. Adams-Watters, Oct 05 2011
Length of n-th run = abs(A088705) + 1. - Reinhard Zumkeller, Dec 11 2011

			a(11)=1 because we have [7,3,1].
G.f. = 1 + x + x^3 + x^4 + x^7 + x^8 + x^10 + x^11 + x^15 + x^16 + x^18 + ...
From _Omar E. Pol_, Nov 30 2009: (Start)
The sequence, displayed as irregular triangle, in which rows length are powers of 2, begins:
1;
1,0;
1,1,0,0;
1,1,0,1,1,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0;
1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0;
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Gary W. Adamson, Comments on A079559
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.5, Recursive generation and relation to a power series, page 74, figure 1.26-E and function A.
Benoit Cloitre, Fractal walk generated by the 130000 first terms (step of unit length moving to right if 0 left if 1) starting at (0,0)
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.[alt source]
Thomas M. Lewis and Fabian Salinas, Optimal pebbling of complete binary trees and a meta-Fibonacci sequence, arXiv:2109.07328 [math.CO], 2021.
F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]
Index entries for characteristic functions

Cf. A000929, A001511, A005187, A006697, A007814, A046699, A055938, A094913, A163988.

Cf. A035263, A066519.

a079559 = p $ tail a000225_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Dec 11 2011

a079559_list = 1 : f [1] where
   f xs = ys ++ f ys where ys = init xs ++ [1] ++ tail xs ++ [0]
-- Reinhard Zumkeller, May 05 2015

g:=product(1+x^(2^n-1),n=1..15): gser:=series(g,x=0,110): seq(coeff(gser,x,n),n=0..104); # Emeric Deutsch, Apr 06 2006
d := n -> if n=1 then 1 else A046699(n)-A046699(n-1) fi; # Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)

row[1] = {1}; row[2] = {1, 0}; row[n_] := row[n] = row[n-1] /. 1 -> Sequence[1, 1, 0]; Table[row[n], {n, 1, 7}] // Flatten (* Jean-François Alcover, Jul 30 2012, after Omar E. Pol *)
CoefficientList[ Series[ Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 104}], x] (* or *)
Nest[ Flatten[# /. {0 -> {0}, 1 -> {1, 1, 0}}] &, {1}, 6] (* Robert G. Wilson v, Sep 08 2014 *)

w="1,";for(i=1,5,print1(w=concat([w,w,"0,"])))

A079559(n,w=[1])=until(n<#w=concat([w,w,[0]]),);w[n+1] \\ M. F. Hasler, Dec 19 2007

{a(n) = if( n<0, 0, polcoeff( prod(k=1, #binary(n+1), 1 + x^(2^k-1), 1 + x * O(x^n)), n))} /* Michael Somos, Aug 03 2009 */

def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a043545(n):
    x=bin(n)[2:]
    return int(max(x)) - int(min(x))
l=[1]
for n in range(1, 101): l+=[a043545(n + 1)*l[n + 1 - a053644(n + 1)], ]
print(l) # Indranil Ghosh, Jun 11 2017

G.f.: Product_{n>=1} (1 + x^(2^n-1)).
a(n) = 1 if n=0, otherwise A043545(n+1)*a(n+1-A053644(n+1)). - Reinhard Zumkeller, Aug 19 2006
a(n) = p(n,1) with p(n,k) = p(n-k,2*k+1) + p(n,2*k+1) if k <= n, otherwise 0^n. - Reinhard Zumkeller, Mar 18 2009
Euler transform is sequence A111113 sequence offset -1. - Michael Somos, Aug 03 2009
G.f.: Product_{k>0} (1 - x^k)^-A111113(k+1). - Michael Somos, Aug 03 2009
a(n) = A108918(n+1) mod 2. - Joerg Arndt, Apr 06 2011
a(n) = A000035(A153000(n)), n >= 1. - Omar E. Pol, Nov 29 2009, Aug 06 2013

Edited by M. F. Hasler, Jan 03 2008

A100661 Quet transform of A006519 (see A101387 for definition). Also, least k such that n+k has at most k ones in its binary representation.

Original entry on oeis.org

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, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 4, 5

Offset: 1

David Wasserman, Jan 14 2005

If n+a(n) has exactly a(n) 1's in binary, then a(n+1) = a(n)+1, but if n+a(n) has less than a(n) 1's, then a(n+1) = a(n)-1. a(n) is the number of terms needed to represent n as a sum of numbers of the form 2^k-1. [Jeffrey Shallit]
Is a(n) = A080468(n+1)+1?
Compute a(n) by repeatedly subtracting the largest number 2^k-1<=n until zero is reached. The number of times a term was subtracted gives a(n). Examples: 5 = 3 + 1 + 1 ==> a(5) = 3 6 = 3 + 3 ==> a(6) = 2. Replace all zeros in A079559 by -1, then the a(n) are obtained as cumulative sums (equivalent to the generating function given); see fxtbook link. [Joerg Arndt, Jun 12 2006]

			a(4) = 2 because 4+2 (110) has two 1's, but 4+1 (101) has more than one 1.
Conjecture (Joerg Arndt):
a(n) is the number of bits in the binary words of sequence A108918
......A108918.A108918..n..=..n.=.(sum.of.term.2^k-1)
........00001.1.....00001.=..1.=..1
........00011.2.....00010.=..2.=..1.+.1
........00010.1.....00011.=..3.=..3
........00101.2.....00100.=..4.=..3.+.1
........00111.3.....00101.=..5.=..3.+.1.+.1
........00110.2.....00110.=..6.=..3.+.3
........00100.1.....00111.=..7.=..7
........01001.2.....01000.=..8.=..7.+.1
........01011.3.....01001.=..9.=..7.+.1.+.1
........01010.2.....01010.=.10.=..7.+.3
........01101.3.....01011.=.11.=..7.+.3.+.1
........01111.4.....01100.=.12.=..7.+.3.+.1.+.1
........01110.3.....01101.=.13.=..7.+.3.+.3
........01100.2.....01110.=.14.=..7.+.7
........01000.1.....01111.=.15.=.15

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.3, p. 72.
David Wasserman, Quet transform + PARI code [Cached copy]

Cf. A006519, A080468, A101387, A100808.

Records at indices in (essentially) A000325.

hb:= n-> `if`(n=1, 0, 1+hb(iquo (n, 2))):
a:= proc(n) local m, t;
      m:= n;
      for t from 0 while m>0 do
        m:= m - (2^(hb(m+1))-1)
      od; t
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 22 2011

hb[n_] := If[n==1, 0, 1+hb[Quotient[n, 2]]];
a[n_] := Module[{m=n, t}, For[t=0, m>0, t++, m = m - (2^(hb[m+1])-1)]; t];
Array[a, 100] (* Jean-François Alcover, Oct 31 2020, after Alois P. Heinz *)

A100661(n)=
{ /* method: repeatedly subtract Mersenne numbers */
    local(m, ct);
    if ( n<=1, return(n) );
    m = 1;
    while ( n>m, m<<=1 );
    m -= 1;
    while ( m>n, m>>=1 );
    /* here m=2^k-1 and m<=n */
    ct = 0;
    while ( n, while (m<=n, n-=m; ct+=1);  m>>=1 );
    return( ct );
}
vector(100,n,A100661(n)) /* show terms */
/* Joerg Arndt, Jan 22 2011 */

TInverse(v)=
{
    local(l, w, used, start, x);
    l = length(v); w = vector(l); used = vector(l); start = 1;
    for (i = 1, l,
        while (start <= l && used[start], start++);
        x = start;
        for (j = 2, v[i], x++; while (x <= l && used[x], x++));
        if (x > l,
            return (vector(i - 1, k, w[k]))
            , /* else */
            w[i] = x; used[x] = 1
        )
    );
    return(w);
}
PInverse(v)=
{
    local(l, w);
    l = length(v); w = vector(l);
    for (i = 1, l, if (v[i] <= l, w[v[i]] = i));
    return(w);
}
T(v)=
{
    local(l, w, c);
    l = length(v); w = vector(l);
    for (n = 1, l,
        if (v[n],
            c = 0;
            for (m = 1, n - 1, if (v[m] < v[n], c++));
            w[n] = v[n] - c
            , /* else */
            return (vector(n - 1, i, w[i]))
        )
    );
    return(w);
}
Q(v)=T(PInverse(TInverse(v)));
/* compute terms: */
v = vector(150);
for (n = 1, 150, m = n; x = 1; while (!(m%2), m\=2; x *= 2); v[n] = x); Q(v)

A100661 = lambda n: next(k for k in PositiveIntegers() if (n+k).digits(base=2).count(1) <= k) # D. S. McNeil, Jan 23 2011

a(2^k-1) = 1. For 2^k <= n <= 2^(k+1)-2, a(n) = a(n-2^k+1)+1.

G.f.: x*(2*(1-x)*prod(n>=1, (1+x^(2^n-1))) - 1)/((1-x)^2) = x*(1 + 2*x + 1*x^2 + 2*x^3 + 3*x^4 + 2*x^5 + 1*x^6 + 2*x^7 + 3*x^8 + 2*x^9 + ...) [Joerg Arndt, Jun 12 2006]

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

A123390 Triangle read by rows: n-th row starts with n and continues with half the previous value as long as that is even.

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Oct 13 2006

A fractal sequence, generated by the rule a(n) is a new maximum when a(n-1) is odd and a repetition of an earlier value when a(n-1) is even.
From Flávio V. Fernandes, Mar 13 2025: (Start)
a(n) is given by A003602(n) at A001511(n) diagram
  1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9
  . 1 . . . 2 . . . 3 . . . 4 . . .
  . . . 1 . . . . . . . 2 . . . . .
  . . . . . . . 1 . . . . . . . . .
  . . . . . . . . . . . . . . . 1 .
read by backwards 2^n, which is given by A118319(n) at A001511(n) diagram
  1 . 2 . 4 . 5 . 8 . 9 .11 .12 .16
  . 3 . . . 6 . . .10 . . .13 . . .
  . . . 7 . . . . . . .14 . . . . .
  . . . . . . .15 . . . . . . . . .
  . . . . . . . . . . . . . . .31 . - see formula. (End)

			Triangle starts
  1;
  2, 1;
  3;
  4, 2, 1;
  5;
  6, 3;
  7;
  8, 4, 2, 1;
  9;
  10, 5;
  11;
  12, 6, 3;
  13;

Alois P. Heinz, Rows n = 1..10000, flattened

Row lengths are A001511.
Row sums give A129527.
Cf. A120385.
Cf. A003602, A108918, A118319.

T:= proc(n) local m,l; m:=n; l:= m;
      while irem(m, 2, 'm')=0 do l:=l,m od: l
    end:
seq(T(n), n=1..40);  # Alois P. Heinz, Oct 09 2015

Flatten[Function[n, NestWhile[Append[#, Last[#]/2] &, {n}, EvenQ[Last[#]] &]][#] & /@ Range[20]] (* Birkas Gyorgy, Apr 13 2011 *)

a(1) = 1, for n > 1, if a(n-1) is even, a(n) = a(n-1)/2, otherwise a(n) = (max_{k

Ordinal transform of A082850.

a(n) = A003602(A108918(n)). - Flávio V. Fernandes, Mar 13 2025

A217262 Delta sequence for binary words in a minimal-change order (subset-lex Gray code).

Original entry on oeis.org

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

Offset: 0

Joerg Arndt, Sep 29 2012

nonn

Positions of change with a certain Gray code (SL-Gray) for binary words (see example): to keep the sequence independent of the word length we start with the all-ones word, the sequence gives the following changes.  The Gray code is cyclic, so first words skipped can (for fixed word length) be appended to the end.
Alternatively, for words length n, start with the all-zeros word, use transitions (n-2), (n-1), (n-2), (n-3), (n-4), ..., 3, 2, 1, 0, followed by the terms of this sequence until all 2^n words have been visited (see rows 00..05 in the example).
The subset-lex Gray code shown here can be obtained by a reflection process from the (reversed) subset-lexicographic order for binary words given in A108918.
Research problem: Does a two-close Gray code exist for the binary words of length n for all n? One-close Gray codes for binary words exists for n<=6 but not for n=7 (and unlikely for any n>=8, see Fxtbook link).
From Joerg Arndt, Apr 29 2014: (Start)
Sequence can be obtained from A007814 by replacing 0 by 01210, 1 by 3, 2 by 141, 3 by 12521, 4 by 1236321, ..., n by 123..(n-1)(n+2)(n-1)..321. - Joerg Arndt, Apr 29 2014
The consecutive transitions are either one-close (abs(a(n)-a(n-1))=1, most of the time) or 3-close (abs(a(n)-a(n-1))=3): In the Gray code of the 2^n n-bit words all transitions are one-close but for 2^(n-2) - 2 transitions that are 3-close; The Gray codes for n<=3 have only one-close transitions.
(End)
The positions of 0's are twice the terms of A327492. - Andrey Zabolotskiy, Jan 06 2024

			Example for word length 5:
no:    word     transition
00:    .....    .1...  3
01:    1....    1....  4
02:    11...    .1...  3
03:    111..    ..1..  2
04:    1111.    ...1.  1
05:    11111    ....1  0 <--= sequence starts
06:    111.1    ...1.  1
07:    11..1    ..1..  2
08:    11.11    ...1.  1
09:    11.1.    ....1  0
10:    1..1.    .1...  3
11:    1..11    ....1  0
12:    1...1    ...1.  1
13:    1.1.1    ..1..  2
14:    1.111    ...1.  1
15:    1.11.    ....1  0
16:    1.1..    ...1.  1
17:    ..1..    1....  4
18:    ..11.    ...1.  1
19:    ..111    ....1  0
20:    ..1.1    ...1.  1
21:    ....1    ..1..  2
22:    ...11    ...1.  1
23:    ...1.    ....1  0
24:    .1.1.    .1...  3
25:    .1.11    ....1  0
26:    .1..1    ...1.  1
27:    .11.1    ..1..  2
28:    .1111    ...1.  1
29:    .111.    ....1  0
30:    .11..    ...1.  1
31:    .1...    ..1..  2
Append first few words to obtain Gray code for word length 5:
00:    .....    .1...
01:    1....    1....
02:    11...    .1...
03:    111..    ..1..
04:    1111.    ...1.

Joerg Arndt, Table of n, a(n) for n = 0..4095
Joerg Arndt, Matters Computational (The Fxtbook), section 20.3.2 "Adjacent changes (AC) Gray codes", p.400.
Joerg Arndt, C++ code to compute this sequence.
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], (26-May-2014)

Cf. A007814 (transitions for the binary reflected Gray code).

Cf. A108918.

Prepended a(0)=0, Joerg Arndt, Apr 29 2014

A356120 Irregular triangle read by rows: the n-th row lists the values 0..2^n-1 representing all subsets of a set of n elements. When its elements are linearly ordered, the subsets are lexicographically ordered.

Original entry on oeis.org

0, 0, 1, 0, 2, 3, 1, 0, 4, 6, 7, 5, 2, 3, 1, 0, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1, 0, 16, 24, 28, 30, 31, 29, 26, 27, 25, 20, 22, 23, 21, 18, 19, 17, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1, 0, 32, 48, 56, 60, 62, 63, 61, 58, 59, 57, 52, 54, 55, 53, 50, 51, 49, 40, 44, 46, 47, 45, 42

Offset: 0

Valentin Bakoev, Jul 27 2022

The sequence in the n-th row of the triangle is denoted by row(n). It contains the values in the range 0..2^n-1 corresponding to the binary vectors of length n. The integers in row (n), considered as characteristic vectors of the set B_n = {b_n, b_(n-1), ..., b_2, b_1}, whose elements are linearly ordered: b_n < b_(n-1) < ... < b_2 < b_1, define all subsets of B_n in lexicographic order. To obtain row(n) we reason inductively as follows. Obviously, row(0) = 0 = a(0) and corresponds to the empty set {}. Assume that the sequence row(n-1) = i_0, i_1, ..., i_(2^(n-1)-1) is obtained. It defines a lexicographic order of the subsets of B_(n-1) = {b_(n-1) , ..., b_2, b_1} - note that its elements linearly ordered. Then row (n) = i_0, 2^(n-1) + i_0, 2^(n-1) + i_1, ..., 2^(n-1) + i_(2^(n-1)-1), i_1, ..., i_(2^(n-1)-1) defines all subsets of B_n in lexicographic order. In other words, row(n) = 0, (row(n-1) + 2^(n-1)), (row(n-1) without the first term 0), i.e., row(n-1) is taken twice: first, all terms of row(n-1) are incremented by 2^(n-1) and second, the resulting sequence is inserted after the first term of row(n-1), which is always 0 and corresponds to {}.

			For n = 1, 2, 3, the sets B_n, their subsets (the column under B_n), binary characteristic words (column bin.) and corresponding integers (column dec.) are:
B_1 = {c}  bin.  dec. | B_2 = {b, c}  bin.   dec. | B_3 = {a, b, c}   bin.   dec.
      {}    0     0   |       {}       00     0   |       {}          000     0
      {c}   1     1   |       {b}      10     2   |       {a}         100     4
                      |       {b, c}   11     3   |       {a, b}      110     6
                      |          {c}   01     1   |       {a, b, c}   111     7
                                                  |       {a, c}      101     5
                                                  |          {b}      010     2
                                                  |          {b, c}   011     3
                                                  |             {c}   001     1
As seen, when B = {a, b, c}, its subsets {}, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c} are in lexicographic order, the corresponding binary words of length 3 are 000, 100, 110, 111, 101, 010, 011, 001, and so row(3) = 0, 4, 6, 7, 5, 2, 3, 1.
Triangle T(n,k) begins:
      k=0  1  2  3  4  5  6  7 ...
  n=0:  0;
  n=1:  0, 1;
  n=2:  0, 2, 3, 1;
  n=3:  0, 4, 6, 7, 5, 2, 3, 1;
  n=4:  0, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1;
  n=5:  0, 16, 24, 28, 30, 31, 29, 26, 27, 25, 20, 22, 23, 21, 18, 19, 17, 8, 12, 14, 15, 13, 10, 11, 9, 4, 6, 7, 5, 2, 3, 1,
  ...

Donald E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.2.1.3 Exercise 19 (Binomial tree traversed in post-order).

Valentin Bakoev, Table of n, a(n) for n = 0..1023
Joerg Arndt, Matters Computational (The Fxtbook), section 1.26 "Binary words in lexicographic order for subsets", pp. 70-74.
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014-2015.
Valentin Bakoev, An Algorithm for Generating All Subsets in Lexicographic Order, ICAI 2022, pp. 271-275.

Cf. A006516 (row sums), A000225 (main diagonal, the n-th term of row(n)).
row(n) without leading 0, when read in reverse order, gives the first 2^n-1 terms of A108918.
Starting with the n-th term of row(n), columns 0..4 are: A000004, A131577 without 0, A007283, A135092, A110286.

(* computing row(n) *)
n = 5;
Array[row, 2^n];
row[0] = 0; row[1] = 1;
len = 2;
For[i = 2, i <= n, i++,
  For[j = 1, j < len, j++, row[j + len] = row[j]];
  For[j = len, j > 0, j--, row[j] = row[j - 1] + len];
  len = len*2;
];

row(n) is defined as:
row(0) = 0;
row(n) = 0, (2^(n-1)+row(n-1)), (row(n-1)\{0}),
where (2^(n-1) + row(n-1)) means a subsequence obtained by adding 2^(n-1) to every term of row(n-1), and (row(n-1)\{0}) means a subsequence row(n-1) without its first term 0, for n = 0, 1, 2, ...).
Then a(n) is defined as:
a(2^m - 1) = 0, for m = 0, 1, 2, ..., and
a(2^m + k) = 2^(m-1) + a(2^(m-1) + k - 1), for k = 0, 1, ..., 2^(m-1) - 1, and
a(2^m + 2^(m-1) + k) = a(2^(m-1)+k), for k = 0, 1, ..., 2^(m-1) - 2.

Showing 1-7 of 7 results.

cp's OEIS Frontend

A118320 Duplicate of A108918.

Views

Author

Keywords

A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A100661 Quet transform of A006519 (see A101387 for definition). Also, least k such that n+k has at most k ones in its binary representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

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

A123390 Triangle read by rows: n-th row starts with n and continues with half the previous value as long as that is even.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A217262 Delta sequence for binary words in a minimal-change order (subset-lex Gray code).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A356120 Irregular triangle read by rows: the n-th row lists the values 0..2^n-1 representing all subsets of a set of n elements. When its elements are linearly ordered, the subsets are lexicographically ordered.

Views

Author

Keywords

Comments

Examples