A035327 -id:A035327 - cp's OEIS frontend

A066099 Triangle read by rows, in which row n lists the compositions of n in reverse lexicographic order.

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

Offset: 1

Alford Arnold, Dec 30 2001

The representation of the compositions (for fixed n) is as lists of parts, the order between individual compositions (for the same n) is (list-)reversed lexicographic; see the example by Omar E. Pol. - Joerg Arndt, Sep 03 2013
This is the standard ordering for compositions in this database; it is similar to the Mathematica ordering for partitions (A080577). Other composition orderings include A124734 (similar to the Abramowitz & Stegun ordering for partitions, A036036), A108244 (similar to the Maple partition ordering, A080576), etc (see crossrefs).
Factorize each term in A057335; sequence records the values of the resulting exponents. It also runs through all possible permutations of multiset digits.
This can be regarded as a table in two ways: with each composition as a row, or with the compositions of each integer as a row. The first way has A000120 as row lengths and A070939 as row sums; the second has A001792 as row lengths and A001788 as row sums. - Franklin T. Adams-Watters, Nov 06 2006
This sequence includes every finite sequence of positive integers. - Franklin T. Adams-Watters, Nov 06 2006
Compositions (or ordered partitions) are also generated in sequence A101211. - Alford Arnold, Dec 12 2006
The equivalent sequence for partitions is A228531. - Omar E. Pol, Sep 03 2013
The sole partition of zero has no components, not a single component of length one. Hence the first nonempty row is row 1. - Franklin T. Adams-Watters, Apr 02 2014 [Edited by Andrey Zabolotskiy, May 19 2018]
See sequence A261300 for another version where the terms of each composition are concatenated to form one single integer: (0, 1, 2, 11, 3, 21, 12, 111,...). This also shows how the terms can be obtained from the binary numbers A007088, cf. Arnold's first Example. - M. F. Hasler, Aug 29 2015
The k-th composition in the list is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This is described as the standard ordering used in the OEIS, although the sister sequence A228351 is also sometimes considered to be canonical. Both sequences define a bijective correspondence between nonnegative integers and integer compositions. - Gus Wiseman, May 19 2020
First differences of A030303 = positions of bits 1 in the concatenation A030190 (= A030302) of numbers written in binary (A007088). - Indices of record values (= first occurrence of n) are given by A005183: a(A005183(n)) = n, cf. FORMULA for more. - M. F. Hasler, Oct 12 2020
The geometric mean approaches the Somos constant (A112302). - Jwalin Bhatt, Feb 10 2025

			A057335 begins 1 2 4 6 8 12 18 30 16 24 36 ... so we can write
  1 2 1 3 2 1 1 4 3 2 2 1 1 1 1 ...
  . . 1 . 1 2 1 . 1 2 1 3 2 1 1 ...
  . . . . . . 1 . . . 1 . 1 2 1 ...
  . . . . . . . . . . . . . . 1 ...
and the columns here gives the rows of the triangle, which begins
  1
  2; 1 1
  3; 2 1; 1 2; 1 1 1
  4; 3 1; 2 2; 2 1 1; 1 3; 1 2 1; 1 1 2; 1 1 1 1
  ...
From _Omar E. Pol_, Sep 03 2013: (Start)
Illustration of initial terms:
  -----------------------------------
  n  j       Diagram   Composition j
  -----------------------------------
  .               _
  1  1           |_|   1;
  .             _ _
  2  1         |  _|   2,
  2  2         |_|_|   1, 1;
  .           _ _ _
  3  1       |    _|   3,
  3  2       |  _|_|   2, 1,
  3  3       | |  _|   1, 2,
  3  4       |_|_|_|   1, 1, 1;
  .         _ _ _ _
  4  1     |      _|   4,
  4  2     |    _|_|   3, 1,
  4  3     |   |  _|   2, 2,
  4  4     |  _|_|_|   2, 1, 1,
  4  5     | |    _|   1, 3,
  4  6     | |  _|_|   1, 2, 1,
  4  7     | | |  _|   1, 1, 2,
  4  8     |_|_|_|_|   1, 1, 1, 1;
(End)

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..5120 (through compositions of 10)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Gus Wiseman, Statistics, classes, and transformations of standard compositions

Lists of compositions of integers: this sequence (reverse lexicographic order; minus one gives A108730), A228351 (reverse colexicographic order - every composition is reversed; minus one gives A163510), A228369 (lexicographic), A228525 (colexicographic), A124734 (length, then lexicographic; minus one gives A124735), A296774 (length, then reverse lexicographic), A337243 (length, then colexicographic), A337259 (length, then reverse colexicographic), A296773 (decreasing length, then lexicographic), A296772 (decreasing length, then reverse lexicographic), A337260 (decreasing length, then colexicographic), A108244 (decreasing length, then reverse colexicographic), also A101211 and A227736 (run lengths of bits).
Cf. row length and row sums for different splittings into rows: A000120, A070939, A001792, A001788.
Cf. A228531, A096903, A065120, A057335, A055932, A005811, A261300, A007088.
Cf. lists of partitions of integers, or multisets of integers: A026791 and crosserfs therein, A112798 and crossrefs therein.
See link for additional crossrefs pertaining to standard compositions.
A related ranking of finite sets is A048793/A272020.
Cf. A005183, A030190, A030302, A030303, A035327, A036036, A080576, A080577, A106356, A112302, A238279, A333219.

a066099 = (!!) a066099_list
a066099_list = concat a066099_tabf
a066099_tabf = map a066099_row [1..]
a066099_row n = reverse $ a228351_row n
-- (each composition as a row)
-- Peter Kagey, Aug 25 2016

Table[FactorInteger[Apply[Times, Map[Prime, Accumulate @ IntegerDigits[n, 2]]]][[All, -1]], {n, 41}] // Flatten (* Michael De Vlieger, Jul 11 2017 *)
stc[n_] := Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]] // Reverse;
Table[stc[n], {n, 0, 20}] // Flatten (* Gus Wiseman, May 19 2020 *)
Table[Reverse @ LexicographicSort @ Flatten[Permutations /@ Partitions[n], 1], {n, 10}] // Flatten (* Eric W. Weisstein, Jun 26 2023 *)

arow(n) = {local(v=vector(n),j=0,k=0);
   while(n>0,k++; if(n%2==1,v[j++]=k;k=0);n\=2);
   vector(j,i,v[j-i+1])} \\ returns empty for n=0. - Franklin T. Adams-Watters, Apr 02 2014

from itertools import islice
from itertools import accumulate, count, groupby, islice
def A066099_gen():
    for i in count(1):
        yield [len(list(g)) for _,g in groupby(accumulate(int(b) for b in bin(i)[2:]))]
A066099 = list(islice(A066099_gen(), 120))  # Jwalin Bhatt, Feb 28 2025

def a_row(n): return list(reversed(Compositions(n)))
flatten([a_row(n) for n in range(1,6)]) # Peter Luschny, May 19 2018

From M. F. Hasler, Oct 12 2020: (Start)
a(n) = A030303(n+1) - A030303(n).
a(A005183(n)) = n; a(A005183(n)+1) = n-1 (n>1); a(A005183(n)+2) = 1. (End)

Edited with additional terms by Franklin T. Adams-Watters, Nov 06 2006

0th row removed by Andrey Zabolotskiy, May 19 2018

A048793 List giving all subsets of natural numbers arranged in standard statistical (or Yates) order.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

For n>0: first occurrence of n in row 2^(n-1), and when the table is seen as a flattened list at position n*2^(n-1)+1, cf. A005183. - Reinhard Zumkeller, Nov 16 2013

Row n lists the positions of 1's in the reversed binary expansion of n. Compare to triangles A112798 and A213925. - Gus Wiseman, Jul 22 2019

			From _Gus Wiseman_, Jul 22 2019: (Start)
Triangle begins:
  {}
  1
  2
  1  2
  3
  1  3
  2  3
  1  2  3
  4
  1  4
  2  4
  1  2  4
  3  4
  1  3  4
  2  3  4
  1  2  3  4
  5
  1  5
  2  5
  1  2  5
  3  5
(End)

S. Hedayat, N. J. A. Sloane and J. Stufken, Orthogonal Arrays, Springer-Verlag, NY, 1999, p. 249.

Reinhard Zumkeller, Rows n = 0..1000 of triangle, flattened

Cf. A048794.
Row lengths are A000120.
First column is A001511.
Heinz numbers of rows are A019565.
Row sums are A029931.
Reversing rows gives A272020.
Subtracting 1 from each term gives A133457; subtracting 1 and reversing rows gives A272011.
Indices of relatively prime rows are A291166 (see also A326674); arithmetic progressions are A295235; rows with integer average are A326669 (see also A326699/A326700); pairwise coprime rows are A326675.
Cf. A035327, A070939.

#include 
#include 
#define USAGE "Usage: 'A048793 num' where num is the largest number to use creating sets.\n"
#define MAX_NUM 10
#define MAX_ROW 1024
int main(int argc, char *argv[]) {
  unsigned short a[MAX_ROW][MAX_NUM]; signed short old_row, new_row, i, j, end;
  if (argc < 2) { fprintf(stderr, USAGE); return EXIT_FAILURE; }
  end = atoi(argv[1]); end = (end > MAX_NUM) ? MAX_NUM: end;
  for (i = 0; i < MAX_ROW; i++) for ( j = 0; j < MAX_NUM; j++) a[i][j] = 0;
  a[1][0] = 1; new_row = 2;
  for (i = 2; i <= end; i++) {
    a[new_row++ ][0] = i;
    for (old_row = 1; a[old_row][0] != i; old_row++) {
      for (j = 0; a[old_row][j] != 0; j++) { a[new_row][j] = a[old_row][j]; }
      a[new_row++ ][j] = i;
    }
  }
  fprintf(stdout, "Values: 0");
  for (i = 1; a[i][0] != 0; i++) for (j = 0; a[i][j] != 0; j++) fprintf(stdout, ",%d", a[i][j]);
  fprintf(stdout, "\n"); return EXIT_SUCCESS
}

a048793 n k = a048793_tabf !! n !! k
a048793_row n = a048793_tabf !! n
a048793_tabf = [0] : [1] : f [[1]] where
   f xss = yss ++ f (xss ++ yss) where
     yss = [y] : map (++ [y]) xss
     y = last (last xss) + 1
-- Reinhard Zumkeller, Nov 16 2013

T:= proc(n) local i, l, m; l:= NULL; m:= n;
      if n=0 then return 0 fi; for i while m>0 do
      if irem(m, 2, 'm')=1 then l:=l, i fi od; l
    end:
seq(T(n), n=0..50);  # Alois P. Heinz, Sep 06 2014

s[0] = {{}}; s[n_] := s[n] = Join[s[n - 1], Append[#, n]& /@ s[n - 1]]; Join[{0}, Flatten[s[6]]] (* Jean-François Alcover, May 24 2012 *)
Table[Join@@Position[Reverse[IntegerDigits[n,2]],1],{n,30}] (* Gus Wiseman, Jul 22 2019 *)

Constructed recursively: subsets that include n are obtained by appending n to all earlier subsets.

More terms from Larry Reeves (larryr(AT)acm.org), Apr 11 2000

A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 11, 12, 13, 14, 14, 15, 16, 17, 15, 16, 17, 18, 18, 19, 20, 21, 7, 8, 9, 10, 10, 11, 12, 13, 11, 12, 13, 14, 14, 15, 16

Offset: 0

N. J. A. Sloane

Write n in base 2, n = sum b(i)*2^(i-1), then a(n) = sum b(i)*i. - Benoit Cloitre, Jun 09 2002
May be regarded as a triangular array read by rows, giving weighted sum of compositions in standard order. The standard order of compositions is given by A066099. - Franklin T. Adams-Watters, Nov 06 2006
Sum of all positive integer roots m_i of polynomial {m,k} - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015
Also the sum of binary indices of n, where a binary index of n (A048793) is any position of a 1 in its reversed binary expansion. For example, the binary indices of 11 are {1,2,4}, so a(11) = 7. - Gus Wiseman, May 22 2024

			14 = 8+4+2 so a(7) = 3+2+1 = 6.
Composition number 11 is 2,1,1; 1*2+2*1+3*1 = 7, so a(11) = 7.
The triangle starts:
  0
  1
  2 3
  3 4 5 6
The reversed binary expansion of 18 is (0,1,0,0,1) with 1's at positions {2,5}, so a(18) = 2 + 5 = 7. - _Gus Wiseman_, Jul 22 2019

T. D. Noe, Table of n, a(n) for n = 0..1023
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 10. See also DOI.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A022290 (Fibonacci), A059590 (factorials), A073642, A089625 (primes), A116549, A326031.
Cf. A001793 (row sums), A011782 (row lengths), A059867, A066099, A124757.
Row sums of A048793 and A272020.
Cf. A035327, A056239, A291166, A295235, A326669, A326674, A326675, A326699/A326700.
Contains exactly A000009(n) copies of n.
For length instead of sum we have A000120, complement A023416.
For minimum instead of sum we have A001511, opposite A000012.
For maximum instead of sum we have A029837 or A070939, opposite A070940.
For product instead of sum we have A096111.
The reverse version is A230877, row sums of A371572.
The reverse complement is A359359, row sums of A371571.
The complement is A359400, row sums of A368494.
Numbers k such that a(k) is prime are A372689.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, inverse A048675.
A372471 lists binary indices of primes, row-sums A372429.
Cf. A000009, A030101, A359401, A359402.

a029931 = sum . zipWith (*) [1..] . a030308_row
-- Reinhard Zumkeller, Feb 28 2014

HammingWeight := n -> add(i, i = convert(n, base, 2)):
a := proc(n) option remember; `if`(n = 0, 0,
ifelse(n::even, a(n/2) + HammingWeight(n/2), a(n-1) + 1)) end:
seq(a(n), n = 0..78); # Peter Luschny, Oct 30 2021

a[n_] := (b = IntegerDigits[n, 2]).Reverse @ Range[Length @ b]; Array[a,78,0] (* Jean-François Alcover, Apr 28 2011, after B. Cloitre *)

for(n=0,100,l=length(binary(n)); print1(sum(i=1,l, component(binary(n),i)*(l-i+1)),","))

a(n) = my(b=binary(n)); b*-[-#b..-1]~; \\ Ruud H.G. van Tol, Oct 17 2023

def A029931(n): return sum(i if j == '1' else 0 for i, j in enumerate(bin(n)[:1:-1],1)) # Chai Wah Wu, Dec 20 2022
(C#)
ulong A029931(ulong n) {
    ulong result = 0, counter = 1;
    while(n > 0) {
        if (n % 2 == 1)
          result += counter;
        counter++;
        n /= 2;
    }
    return result;
} // Frank Hollstein, Jan 07 2023

a(n) = a(n - 2^L(n)) + L(n) + 1 [where L(n) = floor(log_2(n)) = A000523(n)] = sum of digits of A048794 [at least for n < 512]. - Henry Bottomley, Mar 09 2001
a(0) = 0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n) + 1, where e1(n) = A000120(n). a(n) = log_2(A029930(n)). - Ralf Stephan, Jun 19 2003
G.f.: (1/(1-x)) * Sum_{k>=0} (k+1)*x^2^k/(1+x^2^k). - Ralf Stephan, Jun 23 2003
a(n) = Sum_{k>=0} A030308(n,k)*A000027(k+1). - Philippe Deléham, Oct 15 2011
a(n) = sum of n-th row of the triangle in A213629. - Reinhard Zumkeller, Jun 17 2012
From Reinhard Zumkeller, Feb 28 2014: (Start)
a(A089633(n)) = n and a(m) != n for m < A089633(n).
a(n) = Sum_{k=1..A070939(n)} k*A030308(n,k-1). (End)
a(n) = A073642(n) + A000120(n). - Peter Kagey, Apr 04 2016

More terms from Erich Friedman

A023416 Number of 0's in binary expansion of n.

Original entry on oeis.org

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

Offset: 0

David W. Wilson

Another version (A080791) has a(0) = 0.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6.
Jean-Paul Allouche and Jeffrey O. Shallit, Infinite products associated with counting blocks in binary strings, J. London Math. Soc.39 (1989) 193-204.
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
Alex S. A. Alochukwu, Audace A. V. Dossou-Olory, Fadekemi J. Osaye, Valisoa R. M. Rakotonarivo, Shashank Ravichandran, Sarah J. Selkirk, Hua Wang, and Hays Whitlatch, Characterization of Trees with Maximum Security, arXiv:2411.19188 [math.CO], 2024. See p. 12.
Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, 13 (2010), Article 10.7.3.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, Vol. 12 (2012), #A1. - From _N. J. A. Sloane_, Feb 07 2013
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n

The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652. Partial sums see A059015.
With initial zero and shifted right, same as A080791.
Cf. A055641 (for base 10), A188859.

a023416 0 = 1
a023416 1 = 0
a023416 n = a023416 n' + 1 - m where (n', m) = divMod n 2
a023416_list = 1 : c [0] where c (z:zs) = z : c (zs ++ [z+1,z])
-- Reinhard Zumkeller, Feb 19 2012, Jun 16 2011, Mar 07 2011

A023416 := proc(n)
    if n = 0 then
        1;
    else
        add(1-e,e=convert(n,base,2)) ;
    end if;
end proc: # R. J. Mathar, Jul 21 2012

Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 100} ]
DigitCount[Range[0,110],2,0] (* Harvey P. Dale, Jan 10 2013 *)

a(n)=if(n==0,1,n=binary(n); sum(i=1, #n, !n[i])) \\ Charles R Greathouse IV, Jun 10 2011

a(n)=if(n==0,1,#binary(n)-hammingweight(n)) \\ Charles R Greathouse IV, Nov 20 2012

a(n) = if(n == 0, 1, 1+logint(n,2) - hammingweight(n))  \\ Gheorghe Coserea, Sep 01 2015

def A023416(n): return n.bit_length()-n.bit_count() if n else 1 # Chai Wah Wu, Mar 13 2023

a(n) = 1, if n = 0; 0, if n = 1; a(n/2)+1 if n even; a((n-1)/2) if n odd.
a(n) = 1 - (n mod 2) + a(floor(n/2)). - Marc LeBrun, Jul 12 2001
G.f.: 1 + 1/(1-x) * Sum_{k>=0} x^(2^(k+1))/(1+x^2^k). - Ralf Stephan, Apr 15 2002
a(n) = A070939(n) - A000120(n).
a(n) = A008687(n+1) - 1.
a(n) = A000120(A035327(n)).
From Hieronymus Fischer, Jun 12 2012: (Start)
a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/2^j) - floor(n/2^j + 1/2)), where m=floor(log_2(n)).
General formulas for the number of digits <= d in the base p representation n, where 0 <= d < p.
a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/p^j) - floor(n/p^j + (p-d-1)/p)), where m=floor(log_p(n)).
G.f.: 1 + (1/(1-x))*Sum_{j>=0} ((1-x^(d*p^j))*x^p^j + (1-x^p^j)*x^p^(j+1)/(1-x^p^(j+1))). (End)
Product_{n>=1} ((2*n)/(2*n+1))^((-1)^a(n)) = sqrt(2)/2 (A010503) (see Allouche & Shallit link). - Michel Marcus, Aug 31 2014
Sum_{n>=1} a(n)/(n*(n+1)) = 2 - 2*log(2) (A188859) (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Jeffrey Shallit, Simon Plouffe

Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...) and A014577; identical to the latter except starting 1, 1, 0, ...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g., A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - Gary W. Adamson, Jun 21 2012
Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - Jianing Song, Apr 20 2019

			Considered as a triangle with 2^k terms per row, the first few rows are:
  1
  2, 1
  2, 3, 2, 1
  2, 3, 4, 3, 2, 3, 2, 1
  ...
The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - _Gary W. Adamson_, Jun 20 2012

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook).
J.-P. Allouche, G.-N. Han and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Danielle Cox and Karyn McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, Selected Papers on Fun and Games, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
Sara Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289. Also first author's copy. Their "variation" v(k) at definition 3.4 is a(k).
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Index entries for "core" sequences.
Index entries for sequences related to binary expansion of n.

Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
Partial sums of A112347. Recursion depth of A035327.
Cf. A000120, A003188.

import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
   f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011

A005811 := proc(n)
    local i, b, ans;
    if n = 0 then
        return 0 ;
    end if;
    ans := 1;
    b := convert(n, base, 2);
    for i from nops(b)-1 to 1 by -1 do
        if b[ i+1 ]<>b[ i ] then
            ans := ans+1
        fi
    od;
    return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 01 2023

Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 11 2024 *)

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))

a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014

a(n) = hammingweight(bitxor(n, n>>1));  \\ Gheorghe Coserea, Sep 03 2015

def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, Aug 14 2001
a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - Ralf Stephan, May 02 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson, Oct 19 2003
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - Ralf Stephan, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
a(n) = A000120(A003188(n)). - Amiram Eldar, Jul 11 2024

Additional description from Wouter Meeussen

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

Offset: 0

N. J. A. Sloane

Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.
A version of the children's game "One potato, two potato, ...".
a(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010
By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2.  This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013
Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013
For n > 0: a(n) = n + 1 - A080079(n). - Reinhard Zumkeller, Apr 14 2014
In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016
In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2*A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020

			From _Omar E. Pol_, Jun 09 2009: (Start)
Written as an irregular triangle the sequence begins:
  0;
  1;
  1,3;
  1,3,5,7;
  1,3,5,7,9,11,13,15;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,
   43,45,47,49,51,53,55,57,59,61,63;
...
(End)
From _Omar E. Pol_, Nov 03 2018: (Start)
An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:
   n   a(n)       Diagram
   0    0     _
   1    1    |_|_ _
   2    1      |_| |
   3    3      |_ _|_ _ _ _
   4    1          |_| | | |
   5    3          |_ _| | |
   6    5          |_ _ _| |
   7    7          |_ _ _ _|
(End)

Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.
M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

Iain Fox, Table of n, a(n) for n = 0..100000 (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniel Erman and Brady Haran, The Josephus Problem, Numberphile video (2016)
Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
Yuri Nikolayevsky and Ioannis Tsartsaflis, Cohomology of N-graded Lie algebras of maximal class over Z_2, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus problem
Index entries for sequences related to the Josephus Problem

Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.
Second column, and main diagonal, of triangle A032434.
Cf. A181281 (with s=5), A054995 (with s=3).
Column k=2 of A360099.

Require Import ZArith.
Fixpoint a (n : positive) : Z :=
match n with
| xH => 1
| xI n' => (2*(a n') + 1)%Z
| xO n' => (2*(a n') - 1)%Z
end.
(* Stefan Haan, Aug 27 2023 *)

a006257 n = a006257_list !! n
a006257_list =
   0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])
-- Reinhard Zumkeller, Oct 06 2011

[0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016

a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
seq(a(i),i=0..100); # Paul Weisenhorn, Oct 10 2010; corrected by Robert Israel, Jan 13 2016
A006257 := proc(n)
    convert(n,base,2) ;
    ListTools[Rotate](%,-1) ;
    add( op(i,%)*2^(i-1),i=1..nops(%)) ;
end proc: # R. J. Mathar, May 20 2016
A006257 := n -> 2*n  - Bits:-Iff(n, n):
seq(A006257(n), n=0..78); # Peter Luschny, Sep 24 2019

Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *)
Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *)
m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)

a(n)=sum(k=1,n,if(bitxor(n,k)Paul D. Hanna

a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016

import math
def A006257(n):
     return 0 if n==0 else 2*(n-2**int(math.log(n,2)))+1 # Indranil Ghosh, Jan 11 2017

def A006257(n): return bool(n&(m:=1<Chai Wah Wu, Jan 22 2023
(C#)
static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021

To get a(n), write n in binary, rotate left 1 place.
a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun, Jul 11 2001. [Here "msb" = "most significant bit", A053644.]
G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006
a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006
a(n) = n - A035327(n). - K. Spage, Oct 22 2009
a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010
a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013
a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019
For n > 0: a(n) = 2 * A062050(n) - 1. - Frank Hollstein, Oct 25 2021

More terms from Robert G. Wilson v, Sep 21 2003

A228351 Triangle read by rows in which row n lists the compositions (ordered partitions) of n (see Comments lines for definition).

Original entry on oeis.org

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

Offset: 1

Omar E. Pol, Aug 30 2013

The representation of the compositions (for fixed n) is as lists of parts, the order between individual compositions (for the same n) is (list-)reversed co-lexicographic. - Joerg Arndt, Sep 02 2013
Dropping the "(list-)reversed" in the comment above gives A228525.
The equivalent sequence for partitions is A026792.
This sequence lists (without repetitions) all finite compositions, in such a way that, if [P_1, ..., P_r] denotes the composition occupying the n-th position in the list, then (((2*n/2^(P_1)-1)/2^(P_2)-1)/...)/2^(P_r)-1 = 0. - Lorenzo Sauras Altuzarra, Jan 22 2020
The k-th composition in the list is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, and taking first differences. Reversing again gives A066099, which is described as the standard ordering. Both sequences define a bijective correspondence between nonnegative integers and integer compositions. - Gus Wiseman, Apr 01 2020
It follows from the previous comment that A000120(k) is the length of the k-th composition that is listed by this sequence (recall that A000120(k) is the number of 1's in the binary expansion of k). - Lorenzo Sauras Altuzarra, Sep 29 2020

			Illustration of initial terms:
-----------------------------------
n  j     Diagram     Composition j
-----------------------------------
.         _
1  1     |_|         1;
.         _ _
2  1     |_  |       2,
2  2     |_|_|       1, 1;
.         _ _ _
3  1     |_    |     3,
3  2     |_|_  |     1, 2,
3  3     |_  | |     2, 1,
3  4     |_|_|_|     1, 1, 1;
.         _ _ _ _
4  1     |_      |   4,
4  2     |_|_    |   1, 3,
4  3     |_  |   |   2, 2,
4  4     |_|_|_  |   1, 1, 2,
4  5     |_    | |   3, 1,
4  6     |_|_  | |   1, 2, 1,
4  7     |_  | | |   2, 1, 1,
4  8     |_|_|_|_|   1, 1, 1, 1;
.
Triangle begins:
[1];
[2],[1,1];
[3],[1,2],[2,1],[1,1,1];
[4],[1,3],[2,2],[1,1,2],[3,1],[1,2,1],[2,1,1],[1,1,1,1];
[5],[1,4],[2,3],[1,1,3],[3,2],[1,2,2],[2,1,2],[1,1,1,2],[4,1],[1,3,1],[2,2,1],[1,1,2,1],[3,1,1],[1,2,1,1],[2,1,1,1],[1,1,1,1,1];
...
For example [1,2] occupies the 5th position in the corresponding list of compositions and indeed (2*5/2^1-1)/2^2-1 = 0. - _Lorenzo Sauras Altuzarra_, Jan 22 2020
12 --binary expansion--> [1,1,0,0] --reverse--> [0,0,1,1] --positions of 1's--> [3,4] --prepend 0--> [0,3,4] --first differences--> [3,1]. - _Lorenzo Sauras Altuzarra_, Sep 29 2020

Peter Kagey, Table of n, a(n) for n = 1..10000
Mikhail Kurkov, Comments on A228351
Index entries for sequences that are related to compositions

Row n has length A001792(n-1). Row sums give A001787, n >= 1.
Cf. A000120 (binary weight), A001511, A006519, A011782, A026792, A065120.
A related ranking of finite sets is A048793/A272020.
All of the following consider the k-th row to be the k-th composition, ignoring the coarser grouping by sum.
- Indices of weakly increasing rows are A114994.
- Indices of weakly decreasing rows are A225620.
- Indices of strictly decreasing rows are A333255.
- Indices of strictly increasing rows are A333256.
- Indices of reversed interval rows A164894.
- Indices of interval rows are A246534.
- Indices of strict rows are A233564.
- Indices of constant rows are A272919.
- Indices of anti-run rows are A333489.
- Row k has A124767(k) runs and A333381(k) anti-runs.
- Row k has GCD A326674(k) and LCM A333226(k).
- Row k has Heinz number A333219(k).
Cf. A000120, A029931, A035327, A070939, A233249, A333217, A333218, A333220, A333227, A333627, A333628.
Equals A163510+1, termwise.
Cf. A124734 (increasing length, then lexicographic).
Cf. A296774 (increasing length, then reverse lexicographic).
Cf. A337243 (increasing length, then colexicographic).
Cf. A337259 (increasing length, then reverse colexicographic).
Cf. A296773 (decreasing length, then lexicographic).
Cf. A296772 (decreasing length, then reverse lexicographic).
Cf. A337260 (decreasing length, then colexicographic).
Cf. A108244 (decreasing length, then reverse colexicographic).
Cf. A228369 (lexicographic).
Cf. A066099 (reverse lexicographic).
Cf. A228525 (colexicographic).

a228351 n = a228351_list !! (n - 1)
a228351_list = concatMap a228351_row [1..]
a228351_row 0 = []
a228351_row n = a001511 n : a228351_row (n `div` 2^(a001511 n))
-- Peter Kagey, Jun 27 2016

# Program computing the sequence:
A228351 := proc(n) local c, k, L, N: L, N := [], [seq(2*r, r = 1 .. n)]: for k in N do c := 0: while k != 0 do if gcd(k, 2) = 2 then k := k/2: c := c+1: else L := [op(L), op(c)]: k := k-1: c := 0: fi: od: od: L[n]: end: # Lorenzo Sauras Altuzarra, Jan 22 2020
# Program computing the list of compositions:
List := proc(n) local c, k, L, M, N: L, M, N := [], [], [seq(2*r, r = 1 .. 2^n-1)]: for k in N do c := 0: while k != 0 do if gcd(k, 2) = 2 then k := k/2: c := c+1: else L := [op(L), c]: k := k-1: c := 0: fi: od: M := [op(M), L]: L := []: od: M: end: # Lorenzo Sauras Altuzarra, Jan 22 2020

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Differences[Prepend[bpe[n],0]],{n,0,30}] (* Gus Wiseman, Apr 01 2020 *)

from itertools import count, islice
def A228351_gen(): # generator of terms
    for n in count(1):
        k = n
        while k:
            yield (s:=(~k&k-1).bit_length()+1)
            k >>= s
A228351_list = list(islice(A228351_gen(),30)) # Chai Wah Wu, Jul 17 2023

A326704 BII-numbers of antichains of nonempty sets.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 16, 18, 20, 32, 33, 36, 48, 52, 64, 128, 129, 130, 131, 132, 136, 137, 138, 139, 140, 144, 146, 148, 160, 161, 164, 176, 180, 192, 256, 258, 260, 264, 266, 268, 272, 274, 276, 288, 292, 304, 308, 320, 512, 513, 516, 520, 521, 524

Offset: 1

Gus Wiseman, Jul 21 2019

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, it follows that the BII-number of {{2},{1,3}} is 18.

Elements of a set-system are sometimes called edges. In an antichain of sets, no edge is a subset or superset of any other edge.

			The sequence of all antichains of nonempty sets together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  16: {{1,3}}
  18: {{2},{1,3}}
  20: {{1,2},{1,3}}
  32: {{2,3}}
  33: {{1},{2,3}}
  36: {{1,2},{2,3}}
  48: {{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..7580
John Tyler Rascoe, Python Program.

Antichains of sets are counted by A000372.
Antichains of nonempty sets are counted by A014466.
MM-numbers of antichains of multisets are A316476.
BII-numbers of chains of nonempty sets are A326703.
Cf. A000120, A029931, A035327, A048793, A070939, A291166, A302521, A326031, A326675, A326701, A326702.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Select[Range[100],stableQ[bpe/@bpe[#],SubsetQ]&]

Python
```
# see linked program
```

A326701 BII-numbers of set partitions.

Original entry on oeis.org

0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 16, 18, 32, 33, 64, 128, 129, 130, 131, 132, 136, 137, 138, 139, 140, 144, 146, 160, 161, 192, 256, 258, 264, 266, 288, 512, 513, 520, 521, 528, 1024, 1032, 2048, 2049, 2050, 2051, 2052, 4096, 4098, 8192, 8193, 16384, 32768, 32769

Offset: 1

Gus Wiseman, Jul 21 2019

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, and {{2},{1,3}} is a set partition, it follows that 18 belongs to the sequence.

			The sequence of all set partitions together with their BII numbers begins:
    0: {}
    1: {{1}}
    2: {{2}}
    3: {{1},{2}}
    4: {{1,2}}
    8: {{3}}
    9: {{1},{3}}
   10: {{2},{3}}
   11: {{1},{2},{3}}
   12: {{1,2},{3}}
   16: {{1,3}}
   18: {{2},{1,3}}
   32: {{2,3}}
   33: {{1},{2,3}}
   64: {{1,2,3}}
  128: {{4}}
  129: {{1},{4}}
  130: {{2},{4}}
  131: {{1},{2},{4}}
  132: {{1,2},{4}}
  136: {{3},{4}}

John Tyler Rascoe, Table of n, a(n) for n = 1..10000

MM-numbers of set partitions are A302521.
BII-numbers of chains of nonempty sets are A326703.
BII-numbers of antichains of nonempty sets are A326704.
Cf. A000120, A029931, A035327, A048793, A070939, A291166, A326031, A326675, A326702.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,1000],UnsameQ@@Join@@bpe/@bpe[#]&]

from itertools import chain, count, combinations, islice
from sympy.utilities.iterables import multiset_partitions
def a_gen():
    yield 0
    for n in count(1):
        t = []
        for i in chain.from_iterable(combinations(range(1,n+1),r) for r in range(n+1)):
            if n in i:
                for j in multiset_partitions(i):
                    t.append(sum(2**(sum(2**(m-1) for m in k)-1) for k in j))
        yield from sorted(t)
A326701_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, May 24 2024

A061601 9's complement of n: a(n) = 10^d - 1 - n where d is the number of digits in n. If a is a digit in n replace it with 9 - a.

Original entry on oeis.org

9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28

Offset: 0

Amarnath Murthy, May 19 2001

A109002 and A178500 give record values and where they occur: A109002(n+1)=a(A178500(n)) and a(m)<A109002(n+1) for m<A178500(n). - Reinhard Zumkeller, May 28 2010
If n is divisible by 3, so is a(n). The same goes for 9. - Alonso del Arte, Dec 01 2011
For n > 0, a(n-1) consists of the A055642(n) least significant digits of the 10-adic integer -n. - Stefano Spezia, Jan 21 2021

			a(7) = 2 = 10 - 1 -7. a(123) = 1000 -1 -123 = 876.

Kjartan Poskitt, Murderous Maths: Numbers, The Key to the Universe, Scholastic Ltd, 2002. See p 159.

Indranil Ghosh, Table of n, a(n) for n = 0..25000 (terms 0..1000 from Harry J. Smith)

Cf. A035327, A171960.
Cf. A055120.
See A267193 for complement obverse of n.

a061601 n = if n <= 9 then 9 - n else 10 * ad n' + 9 - d
            where (n',d) = divMod n 10
-- Reinhard Zumkeller, Feb 21 2014, Oct 04 2011

A061601 := proc(n)
        10^A055642(n)-1-n ;
end proc: # R. J. Mathar, Nov 30 2011

nineComplement[n_] := FromDigits[Table[9, {Length[IntegerDigits[n]]}] - IntegerDigits[n]]; Table[nineComplement[n], {n, 0, 71}] (* Alonso del Arte, Nov 30 2011 *)

A061601(n)=my(e=length(Str(n)));10^e-1 - n; \\ Joerg Arndt, Aug 28 2013

def A061601(n):
    return 10**len(str(n))-1-n # Indranil Ghosh, Jan 30 2017

a(n) = if n<10 then 9 - n else 10*a([n/10]) + 9 - n mod 10. - Reinhard Zumkeller, Jan 20 2010

a(n) <= 9n - 1. - Charles R Greathouse IV, Nov 15 2022

Corrected and extended by Matthew Conroy, Jan 19 2002

cp's OEIS Frontend

A066099 Triangle read by rows, in which row n lists the compositions of n in reverse lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Sage

Formula

Extensions

A048793 List giving all subsets of natural numbers arranged in standard statistical (or Yates) order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

Formula

Extensions

A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A023416 Number of 0's in binary expansion of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.