cp's OEIS Frontend

As with decimal reversal, initial zeros are ignored; otherwise, the reverse of 1 would be 1000000... ad infinitum.

Numerators of the binary van der Corput sequence. - Eric Rowland, Feb 12 2008

It seems that in most cases A030101(x) = A000265(x) and that if A030101(x) <> A000265(x), the next time A030101(y) = A000265(x), A030101(x) = A000265(y). Also, it seems that if a pair of values exist at one index, they will exist at any index where one of them exist. It also seems like the greater of the pair always shows up on A000265 first. - Dylan Hamilton, Aug 04 2010

The number of occasions A030101(n) = A000265(n) before n = 2^k is A053599(k) + 1. For n = 0..2^19, the sequences match less than 1% of the time. - Andrew Woods, May 19 2012

For n > 0: a(a(n)) = n if and only if n is odd; a(A006995(n)) = A006995(n). - Juli Mallett, Nov 11 2010, corrected: Reinhard Zumkeller, Oct 21 2011

n is binary palindromic if and only if a(n) = n. - Reinhard Zumkeller, corrected: Jan 17 2012, thanks to Hieronymus Fischer, who pointed this out; Oct 21 2011

Given any n > 1, the set of numbers A030109(i) = (A030101(i) - 1)/2 for indexes i ranging from 2^n to 2^(n + 1) - 1 is a permutation of the set of consecutive integers {0, 1, 2, ..., 2^n - 1}. This is important in the standard FFT algorithms (starting or ending bit-reversal permutation). - Stanislav Sykora, Mar 15 2012

Row n of A030308 gives the binary digits of a(n), prepended with zero at even positions. - Reinhard Zumkeller, Jun 17 2012

The binary van der Corput sequence is the infinite sequence of fractions { A030101(n)/A062383(n), n = 0, 1, 2, 3, ... }, and begins 0, 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16, 5/16, 13/16, 3/16, 11/16, 7/16, 15/16, 1/32, 17/32, 9/32, 25/32, 5/32, 21/32, 13/32, 29/32, 3/32, 19/32, 11/32, 27/32, 7/32, 23/32, 15/32, 31/32, 1/64, 33/64, 17/64, 49/64, ... - N. J. A. Sloane, Dec 01 2019

Record highs occur at n = A209492(m) (for n>=1) with values a(n) = A224195(m) (for n>=3). - Bill McEachen, Aug 02 2023

CatalanRankGlobal given in A057117 and the other Maple procedures in A056539.

Composition with A057163 gives Donaghey's Map M (A057505/A057506).

The original name was "Bit-reverse of n, including as many leading as trailing zeros." - Antti Karttunen, Dec 25 2024

A permutation of integers consisting only of fixed points and pairs. a(n)=n when n is a binary palindrome (including as many leading as trailing zeros), otherwise a(n)=A003010(n) (i.e. n has no axis of symmetry). A057890 gives the palindromes (fixed points, akin to A006995) while A057891 gives the "antidromes" (pairs). See also A280505.

This is multiplicative in domain GF(2)[X], i.e. with carryless binary arithmetic. A193231 is another such permutation of natural numbers. - Antti Karttunen, Dec 25 2024

Row n has A005811(n) elements. In rows 2^(k-1)..2^k-1 we have all the compositions (ordered partitions) of k. Other orderings of compositions: A066099, A108244, and A124734. - Jason Kimberley, Feb 09 2013

A043276(n) = largest term in n-th row. - Reinhard Zumkeller, Dec 16 2013

From the first comment it follows that we have a bijection between the positive integers and the set of all compositions. - Emeric Deutsch, Jul 11 2017

From Robert Israel, Jan 23 2018: (Start)

If n is even, row 2*n is row n with its last element incremented by 1, and row 2*n+1 is row n with 1 appended.

If n is odd, row 2*n+1 is row n with its last element incremented by 1, and row 2*n is row n with 1 appended. (End)

a(0) could be considered to be 0 if the binary representation of zero were chosen to be the empty string. - Jason Kimberley, Sep 19 2011

From Bernard Schott, Jun 15 2021: (Start)

Except for a(0) = 1, every term is even.

For each q >= 0, there is one and only one odd number h such that a(n) = 2*q iff n = h*2^m-1 for m >= 1 when q = 0, and for m >= 0 when q >= 1 (see A345401 and some examples below).

a(n) = 0 iff n = 2^m-1 for m >= 1 (Mersenne numbers) (A000225).

a(n) = 2 iff n = 3*2^m-1 for m >= 0 (A153893).

a(n) = 4 iff n = 7*2^m-1 for m >= 0 (A086224).

a(n) = 6 iff n = 5*2^m-1 for m >= 0 (A153894).

a(n) = 8 iff n = 15*2^m-1 for m >= 0 (A196305).

a(n) = 10 iff n = 11*2^m-1 for m >= 0 (A086225).

a(n) = 12 iff n = 13*2^m-1 for m >= 0 (A198274).

For k >= 1, a(n) = 2^k iff n = (2^(k+1)-1)*2^m - 1 for m >= 0.

Explanation for a(n) = 2:

For m >= 0, A153893(m) = 3*2^m-1 -> 1011...11 -> 0100...00 -> 10 -> 2 where 1011...11_2 is 10 followed by m 1's. (End)

Conjecture: For all n, a(A054429(n)) = A054429(a(n)), i.e. A054429 acts as a homomorphism (automorphism) of the cyclic group generated by this permutation. This implies also a weaker conjecture given in A209860.

From Gus Wiseman, Aug 24 2021: (Start)

As a triangle with row lengths 2^n, T(n,k) for n > 0 appears (verified up to n = 2^15) to be the unique nonnegative integer whose binary indices are the k-th subset of {1..n} containing n. Here, a binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion, and sets are sorted first by length, then lexicographically. For example, the triangle begins:

1

2 3

4 5 6 7

8 9 10 12 11 13 14 15

16 17 18 20 24 19 21 25 22 26 28 23 27 29 30 31

Mathematica: Table[Total[2^(Append[#,n]-1)]&/@Subsets[Range[n-1]],{n,5}]

Row lengths are A000079 (shifted right). Also Column k = 1.

Row sums are A010036.

Using reverse-lexicographic order gives A059893.

Using lexicographic order gives A059894.

Taking binary indices to prime indices gives A339195 (or A019565).

The ordering of sets is A344084.

A version using Heinz numbers is A344085.

(End)

To make this a permutation of nonnegative integers, we subtract one from each run count except for the most significant run, e.g. a(11) = 9, as 11 = 1011 and 9+1 = 10 = 5^1 * 3^(1-1) * 2^(2-1).

This is not a permutation of integers: a(25) = 25 = 5*5 = a(19) is the first case which breaks the injectivity. However, the first 24 terms are equal with A057889, which is a GF(2)[X]-analog of this sequence and which in contrary to this, is bijective. This stems from the fact that the set of irreducible GF(2)[X] polynomials (A014580) is closed under bit-reversal (A056539), while primes (A000040) are not.

Sequence A290078 gives the positions n where the ratio a(n)/n obtains new record values.

Note, instead of A056539 we could as well use A057889 to reverse the bits of n, and also A030101 when restricted to odd primes.

Partial sums of number of runs in binary expansion of n (n>0). Partial sums of number of 1's in Gray code for n. The subsequence of squares in this partial sum begins 0, 1, 4, 9, 144, 169, 256, 289, 324 (since we also have 32 and 128 I wonder about why so many powers). The subsequence of primes in this partial sum begins: 3, 11, 17, 29, 31, 37, 41, 53, 79, 89, 101, 137, 149, 181, 191, 197, 229, 271.

Note: A227744 now gives the squares, which occur at positions given by A227743. - Antti Karttunen, Jul 27 2013

This is a self-inverse permutation of the positive integers.

Old name was: a(0) = 0, and for n>=1, let b(n,m) be the m-th digit, reading left to right, of binary n. (b(n, 1) is the most significant binary digit, which is 1.) Then a(n) is such that b(a(n),1)=1; and if b(n,m)=b(n,m-1) then b(a(n),m) does not = b(a(n),m-1); and if b(n,m) does not = b(n,m-1) then b(a(n), m) = b(a(n),m-1), for all m where 2 <= m <= number binary digits in n.

From Emeric Deutsch, Oct 06 2020: (Start)

a(n) is the index of the composition that is the conjugate of the composition with index n.

The index of a composition is defined to be the positive integer whose binary form has run-lengths (i.e., runs of 1's, runs of 0's, etc. from left to right) equal to the parts of the composition. Example: the composition 1,1,3,1 has index 46 since the binary form of 46 is 101110.

a(18) = 24. Indeed, since the binary form of 18 is 10010, the composition with index 18 is 1,2,1,1 (the run-lengths of 10010); the conjugate of 1,2,1,1 is 2,3 and so the binary form of a(18) is 11000; consequently, a(18) = 24. (End)