A005811 -id:A005811 - cp's OEIS frontend

A324346 Lexicographically earliest positive sequence such that a(i) = a(j) => A005811(i) = A005811(j) and A324055(i) = A324055(j), for all i, j >= 0.

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

Offset: 0

Antti Karttunen, Feb 24 2019

nonn

Restricted growth sequence transform of the ordered pair [A005811(n), A324055(n)].

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for sequences related to binary expansion of n

Cf. A005811, A324055, A324345, A324347.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A005811(n) = hammingweight(bitxor(n, n>>1)); \\ From A005811
A324055(n) = { my(m1=2,m2=1,p=2,mp=p*p); while(n, if(!(n%2), p=nextprime(1+p); mp = p*p, m1 *= p; if(3==(n%4),mp *= p,m2 *= (mp-1)/(p-1))); n>>=1); (m1-m2); };
Aux324346(n) = [A005811(n), A324055(n)];
v324346 = rgs_transform(vector(1+up_to,n,Aux324346(n-1)));
A324346(n) = v324346[1+n];

For all n >= 1, a((2^n)-1) = 2.

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).

Original entry on oeis.org

0, 1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 1, 2, 3, 2, -3, 2, 7, 2, -3, 4, 3, 2, -3, 14, 1, 10, -3, 2, 3, 2, -11, 4, 1, -2, -7, 2, 3, 2, -11, 2, 7, 2, -7, -4, 3, 2, -19, 8, 25, 2, -11, 2, 19, -6, -15, 4, 1, 2, -19, 2, 3, -6, -23, -10, 7, 2, -15, 4, -5, 2, -27, 2, 1, 6, -15, -4, 3, 2, -39, 28, 1, 2, -27, -14, 3, 2, -27, 2, -9, -10, -19, 4, 3, -14, -47, 2, 15, -14, -19, 2, 3, 2, -35, -24

Offset: 1

Antti Karttunen, Apr 04 2000

sign

For all odd primes p, a(p) = +2 because Sum_{a=1..(p-2)} L((a(a+1))/p) = Sum_{a=1..(p-2)} L((1+(a^-1))/p) = -1; i.e. in Gray code expansion of A055094[p], the number of 1-bits is number of 0-bits + 2. However, a(n) = +2 also for some nonprime odd n = A055131.

See problem 9.2.2 in Elementary Number Theory by David M. Burton, ISBN 0-205-06978-9

Indranil Ghosh, Table of n, a(n) for n = 1..4096

A055095 := proc(n)
    2*A005811(A055094(n))-n+1 ;
end proc:
seq(A055095(n),n=1..20) ; # R. J. Mathar, Mar 10 2015

A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];
A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;
a[1] = 0; a[n_] := 2*A005811[A055094[n]] - (n-1);
Array[a, 105] (* Jean-François Alcover, Mar 05 2016 *)

from sympy.ntheory.residue_ntheory import quadratic_residues as q
def a055094(n):
    Q=q(n)
    z=0
    for i in range(1, n):
        z*=2
        if i in Q: z+=1
    return z
def a005811(n): return bin(n^(n>>1))[2:].count("1")
def a(n): return 0 if n == 1 else 2*a005811(a055094(n)) - (n - 1) # Indranil Ghosh, May 13 2017

a(n) = (2*wt(GrayCode(qrs2bincode(n))))-(n-1).

A286558 Ordinal transform of A005811.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 3, 4, 2, 1, 3, 5, 4, 6, 4, 7, 5, 2, 6, 3, 1, 4, 7, 8, 8, 5, 9, 9, 10, 10, 5, 11, 11, 6, 12, 7, 2, 8, 13, 9, 3, 1, 4, 10, 5, 11, 14, 12, 15, 12, 16, 13, 6, 14, 17, 13, 18, 15, 19, 14, 20, 15, 6, 16, 21, 16, 22, 17, 7, 18, 23, 19, 8, 2, 9, 20, 10, 21, 24, 22, 11, 3, 12, 4, 1, 5, 13, 23, 14, 6, 15, 24, 16, 25, 25, 17, 26, 26, 27, 27, 17, 28, 28

Offset: 0

Antti Karttunen, May 21 2017

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences related to binary expansion of n

Cf. A005811.

Cf. A263017, A254524, A286478, A286554 for similar sequences.

A341694 Square array T(n, k) read by antidiagonals upwards, n, k > 0: T(n, k) = A227736(n, k) for k = 1..A005811(n), and T(n, k) = T(n, k - A005811(n)) + ... + T(n, k-1) for k > A005811(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 1, 1, 1, 3, 2, 5, 1, 3, 2, 1, 4, 2, 8, 1, 3, 3, 3, 3, 7, 2, 13, 1, 1, 1, 3, 5, 5, 11, 2, 21, 1, 1, 2, 4, 3, 8, 9, 18, 2, 34, 1, 2, 1, 1, 5, 3, 13, 17, 29, 2, 55, 1, 2, 1, 1, 4, 9, 3, 21, 31, 47, 2, 89, 1

Offset: 1

Rémy Sigrist, Feb 17 2021

This table contains all Fibonacci sequences of order m > 0 with positive terms:
- order 1 corresponds to constant sequences (n in A126646),
- order 2 corresponds to Fibonacci-like sequences (n in A043569),
- order 3 corresponds to tribonacci-like sequences (n in A043570),
- order 4 corresponds to tetranacci-like sequences (n in A043571).
For any n > 0, the row A341746(n) corresponds to the n-th row from which the first term has been removed.

			Array T(n, k) begins:
  n\k|  1  2  3  4  5   6   7   8   9   10   11   12   13    14
  ---+---------------------------------------------------------
    1|  1  1  1  1  1   1   1   1   1    1    1    1    1     1 --> A000012
    2|  1  1  2  3  5   8  13  21  34   55   89  144  233   377 --> A000045
    3|  2  2  2  2  2   2   2   2   2    2    2    2    2     2 --> A007395
    4|  2  1  3  4  7  11  18  29  47   76  123  199  322   521 --> A000032
    5|  1  1  1  3  5   9  17  31  57  105  193  355  653  1201 --> A000213
    6|  1  2  3  5  8  13  21  34  55   89  144  233  377   610 --> A000045
    7|  3  3  3  3  3   3   3   3   3    3    3    3    3     3 --> A010701
    8|  3  1  4  5  9  14  23  37  60   97  157  254  411   665 --> A104449
    9|  1  2  1  4  7  12  23  42  77  142  261  480  883  1624 --> A275778
   10|  1  1  1  1  4   7  13  25  49   94  181  349  673  1297 --> A000288

Rémy Sigrist, Table of n, a(n) for n = 1..11325
Rémy Sigrist, Colored representation of the table for n, k = 1..1024
Rémy Sigrist, PARI program for A341694
Wikipedia, Fibonacci numbers of higher order
Index entries for sequences related to Fibonacci numbers

Cf. A005811, A043569, A043570, A043571, A126646, A136480, A227736, A341699, A341746.

Cf. A000012, A000032, A000045, A000213, A000288, A007395, A010701, A104449, A275778.

PARI
```
See Links section.
```

T(A341746(n), k) = T(n, k+1).

T(n, 1) = A136480(n).

A136004 a(n) = A005811(n) + 4.

Original entry on oeis.org

4, 5, 6, 5, 6, 7, 6, 5, 6, 7, 8, 7, 6, 7, 6, 5, 6, 7, 8, 7, 8, 9, 8, 7, 6, 7, 8, 7, 6, 7, 6, 5, 6, 7, 8, 7, 8, 9, 8, 7, 8, 9, 10, 9, 8, 9, 8, 7, 6, 7, 8, 7, 8, 9, 8, 7, 6, 7, 8, 7, 6, 7, 6, 5, 6, 7, 8, 7, 8, 9, 8, 7, 8, 9, 10, 9, 8, 9, 8, 7, 8, 9, 10, 9, 10, 11, 10, 9, 8, 9, 10, 9, 8, 9

Offset: 0

N. J. A. Sloane, Mar 16 2008

nonn

The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.

Cf. A005811.

Table[Length@ Split@ IntegerDigits[n, 2] - Boole[n == 0] + 4, {n, 0, 93}] (* Michael De Vlieger, Sep 05 2017 *)

A371343 Lexicographically latest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of n and of a(n) have the same length (A070939) and the same number of runs of consecutive equals digits (A005811).

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Mar 24 2024

This sequence is a self-inverse permutation of the nonnegative integers with infinitely many fixed points (for example, all terms of A000225 are fixed points).

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0
   1     1       1          1
   2     2      10         10
   3     3      11         11
   4     6     100        110
   5     5     101        101
   6     4     110        100
   7     7     111        111
   8    14    1000       1110
   9    13    1001       1101
  10    10    1010       1010
  11    11    1011       1011
  12    12    1100       1100
  13     9    1101       1001
  14     8    1110       1000
  15    15    1111       1111

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, Colored scatterplot of the first 2^20 terms (where the color is function of A005811(n))
Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

See A331274 and A337242 for similar sequences.

Cf. A000225, A005811, A070939.

PARI
```
\\ See Links section.
```

A043554 Essentially same as A005811.

Original entry on oeis.org

1, 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

Offset: 0

dead

A000035 Period 2: repeat [0, 1]; a(n) = n mod 2; parity of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Least significant bit of n, lsb(n).
Also decimal expansion of 1/99.
Also the binary expansion of 1/3. - Robert G. Wilson v, Sep 01 2015
a(n) = A134451(n) mod 2. - Reinhard Zumkeller, Oct 27 2007 [Corrected by Jianing Song, Nov 22 2019]
Characteristic function of odd numbers: a(A005408(n)) = 1, a(A005843(n)) = 0. - Reinhard Zumkeller, Sep 29 2008
A102370(n) modulo 2. - Philippe Deléham, Apr 04 2009
Base b expansion of 1/(b^2-1) for any b >= 2 is 0.0101... (A005563 has b^2-1). - Rick L. Shepherd, Sep 27 2009
Let A be the Hessenberg n X n matrix defined by: A[1,j] = j mod 2, A[i,i] := 1, A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = (-1)^n*charpoly(A,1). - Milan Janjic, Jan 24 2010
From R. J. Mathar, Jul 15 2010: (Start)
The sequence is the principal Dirichlet character of the reduced residue system mod 2 or mod 4 or mod 8 or mod 16 ...
Associated Dirichlet L-functions are for example L(2,chi) = Sum_{n>=1} a(n)/n^2 == A111003,
or L(3,chi) = Sum_{n>=1} a(n)/n^3 = 1.05179979... = 7*A002117/8,
or L(4,chi) = Sum_{n>=1} a(n)/n^4 = 1.014678... = A092425/96. (End)
Also parity of the nonnegative integers A001477. - Omar E. Pol, Jan 17 2012
a(n) = (4/n), where (k/n) is the Kronecker symbol. See the Eric Weisstein link. - Wolfdieter Lang, May 28 2013
Also the inverse binomial transform of A131577. - Paul Curtz, Nov 16 2016 [an observation forwarded by Jean-François Alcover]
The emanation sequence for the globe category. That is take the globe category, take the corresponding polynomial comonad, consider its carrier polynomial as a generating function, and take the corresponding sequence. - David Spivak, Sep 25 2020
For n > 0, a(n) is the alternating sum of the product of n increasing and n decreasing odd factors. For example, a(4) = 1*7 - 3*5 + 5*3 - 7*1 and a(5) = 1*9 - 3*7 + 5*5 - 7*3 + 9*1. - Charlie Marion, Mar 24 2022

			G.f. = x + x^3 + x^5 + x^7 + x^9 + x^11 + x^13 + x^15 + ... - _Michael Somos_, Feb 20 2024

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

David Wasserman, Table of n, a(n) for n = 0..1000
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
Clark Kimberling, A Combinatorial Classification of Triangle Centers on the Line at Infinity, J. Int. Seq., Vol. 22 (2019), Article 19.5.4.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function
Eric Weisstein's World of Mathematics, Kronecker Symbol
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29
Index entries for "core" sequences
Index entries for sequences that are fixed points of mappings
Index entries for characteristic functions
Index entries for linear recurrences with constant coefficients, signature (0,1).

Ones complement of A059841.
Cf. A053644 for most significant bit.
This is Guy Steele's sequence GS(1, 2) (see A135416).
Period k zigzag sequences: this sequence (k=2), A007877 (k=4), A260686 (k=6), A266313 (k=8), A271751 (k=10), A271832 (k=12), A279313 (k=14), A279319 (k=16), A158289 (k=18).
Cf. A154955 (Mobius transform), A131577 (binomial transform).
Cf. A111003 (Dgf at s=2), A233091 (Dgf at s=3), A300707 (Dgf at s=4).
Parity of A005811.

a000035 n = n `mod` 2  -- James Spahlinger, Oct 08 2012

a000035_list = cycle [0,1]  -- Reinhard Zumkeller, Jan 06 2012

A000035 := n->n mod 2;
[ seq(i mod 2, i=0..100) ];

PadLeft[{},110,{0,1}] (* Harvey P. Dale, Sep 25 2011 *)

A000035(n):=mod(n,2)$
makelist(A000035(n),n,0,30); /* Martin Ettl, Nov 12 2012 */

PARI
```
a(n)=n%2;
```

a(n)=direuler(p=1,100,if(p==2,1,1/(1-X)))[n] /* Ralf Stephan, Mar 27 2015 */

def A000035(n): return n & 1 # Chai Wah Wu, May 25 2022

(define (A000035 n) (mod n 2)) ;; For R6RS. Use modulo in older Schemes like MIT/GNU Scheme. - Antti Karttunen, Mar 21 2017

a(n) = (1 - (-1)^n)/2.
a(n) = n mod 2.
a(n) = 1 - a(n-1).
Multiplicative with a(p^e) = p mod 2. - David W. Wilson, Aug 01 2001
G.f.: x/(1-x^2). E.g.f.: sinh(x). - Paul Barry, Mar 11 2003
a(n) = (A000051(n) - A014551(n))/2. - Mario Catalani (mario.catalani(AT)unito.it), Aug 30 2003
a(n) = ceiling((-2)^(-n-1)). - Reinhard Zumkeller, Apr 19 2005
Dirichlet g.f.: (1-1/2^s)*zeta(s). - R. J. Mathar, Mar 04 2011
a(n) = ceiling(n/2) - floor(n/2). - Arkadiusz Wesolowski, Sep 16 2012
a(n) = ceiling( cos(Pi*(n-1))/2 ). - Wesley Ivan Hurt, Jun 16 2013
a(n) = floor((n-1)/2) - floor((n-2)/2). - Mikael Aaltonen, Feb 26 2015
Dirichlet g.f.: L(chi(2),s) with chi(2) the principal Dirichlet character modulo 2. - Ralf Stephan, Mar 27 2015
a(n) = 0^^n = 0^(0^(0...)) (n times), where we take 0^0 to be 1. - Natan Arie Consigli, May 02 2015
Euler transform and inverse Moebius transform of length 2 sequence [0, 1]. - Michael Somos, Feb 20 2024

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

Original entry on oeis.org

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

A006068 a(n) is Gray-coded into n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Equivalently, if binary expansion of n has m bits (say), compute derivative of n (A038554), getting sequence n' of length m-1; sort on n'.
Inverse of sequence A003188 considered as a permutation of the nonnegative integers, i.e., a(A003188(n)) = n = A003188(a(n)). - Howard A. Landman, Sep 25 2001
The sequence exhibits glide reflections that grow fractally. These show up well on the scatterplot, also audibly using the "listen" link. - Peter Munn, Aug 18 2019
Each bit at bit-index k (counted from the right hand end, with the least significant bit having bit-index 0) in the binary representation of a(n) is the parity of the number of 1's among the bits of the binary representation of n that have a bit-index of k or higher. - Frederik P.J. Vandecasteele, May 26 2025

			The first few values of n' are -,-,1,0,10,11,01,00,100,101,111,110,010,011,001,000,... (for n=0..15) and to put these in lexicographic order we must take n in the order 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,...

M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
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..1023
Joerg Arndt, Matters Computational (The Fxtbook), section 1.16 Gray code, C code inverse_gray_code() with "version 3" giving the PARI code here.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 22.
Paul Tarau, Isomorphic Data Encodings and their Generalization to Hylomorphisms on Hereditarily Finite Data Types; see also alternate link.
Index entries for sequences that are permutations of the natural numbers

Cf. A038554, A005811, A003188, A014550, A003100, A265263, A377404.
Cf. A054429, A180200. - Reinhard Zumkeller, Aug 15 2010
Cf. A000079, A055975 (first differences), A209281 (binary weight).
A003987, A010060 are used to express relationship between terms of this sequence.

a006068 n = foldl xor 0 $
                  map (div n) $ takeWhile (<= n) a000079_list :: Integer
-- Reinhard Zumkeller, Apr 28 2012

a:= proc(n) option remember; `if`(n<2, n,
      Bits[Xor](n, a(iquo(n, 2))))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 17 2018

a[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]; a[0]=0; Table[a[n], {n, 0, 69}] (* Jean-François Alcover, Jul 19 2012, after Paul D. Hanna *)
Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 70}] (* Jan Mangaldan, Mar 20 2013 *)

{a(n)=local(B=n);for(k=1,floor(log(n+1)/log(2)),B=bitxor(B,n\2^k));B} /* Paul D. Hanna, Jan 18 2012 */

/* the following routine needs only O(log_2(n)) operations */
a(n)= {
    my( s=1, ns );
    while ( 1,
        ns = n >> s;
        if ( 0==ns, break() );
        n = bitxor(n, ns);
        s <<= 1;
    );
    return ( n );
} /* Joerg Arndt, Jul 19 2012 */

def a(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Joerg Arndt

nmax <- 63 # by choice
a <- vector()
for(n in 1:nmax){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  level <- 0; anbit <- nbit; anbit.s <- nbit
  while(sum(anbit.s) > 0){
    s <- 2^level; if(s > length(anbit.s)) break
    anbit.s <- c(anbit[-(1:s)], rep(0,s))
    anbit <- bitwXor(anbit, anbit.s)
    level <- level + 1
  }
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
(a <- c(0,a))
# Yosu Yurramendi, Oct 12 2021, after PARI code by Joerg Arndt

a(n) = 2*a(ceiling((n+1)/2)) + A010060(n-1). If 3*2^(k-1) < n <= 2^(k+1), a(n) = 2^(k+1) - 1 - a(n-2^k); if 2^(k+1) < n <= 3*2^k, a(n) = a(n-2^k) + 2^k. - Henry Bottomley, Jan 10 2001
a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ... XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x. - Paul D. Hanna, Jun 04 2002
a(n) XOR [a(n)/2] = n. - Paul D. Hanna, Jan 18 2012
A066194(n) = a(n-1) + 1, n>=1. - Philippe Deléham, Apr 29 2005
a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)). - Reinhard Zumkeller, Aug 10 2010
a(n XOR m) = a(n) XOR a(m), where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Dec 14 2019
a(0) = 0. For all n >= 0 if a(n) is even a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)+1, else a(2*n) = 2*a(n)+1, a(2*n+1) = 2*a(n). - Yosu Yurramendi, Oct 12 2021
Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
a(n) = 2*A265263(n) - 2*A377404(n) - A010060(n). - Alan Michael Gómez Calderón, Jun 26 2025

More terms from Henry Bottomley, Jan 10 2001

cp's OEIS Frontend

A324346 Lexicographically earliest positive sequence such that a(i) = a(j) => A005811(i) = A005811(j) and A324055(i) = A324055(j), for all i, j >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A055095 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Python

Formula

A286558 Ordinal transform of A005811.

Views

Author

Keywords

Links

Crossrefs

A341694 Square array T(n, k) read by antidiagonals upwards, n, k > 0: T(n, k) = A227736(n, k) for k = 1..A005811(n), and T(n, k) = T(n, k - A005811(n)) + ... + T(n, k-1) for k > A005811(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A136004 a(n) = A005811(n) + 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A371343 Lexicographically latest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of n and of a(n) have the same length (A070939) and the same number of runs of consecutive equals digits (A005811).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A043554 Essentially same as A005811.

Views

Author

Keywords

A000035 Period 2: repeat [0, 1]; a(n) = n mod 2; parity of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

Maxima

PARI

PARI

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).