cp's OEIS Frontend

Sequence consists of all numbers with binary representation 1(011)*.

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

A self-inverse permutation of the natural numbers.

a(n)=n if and only if A081242(n) is a palindrome. - Clark Kimberling, Mar 12 2003

a(n) is the position in B of the reversal of the n-th term of B, where B is the left-to-right binary enumeration sequence (A081242 with the empty word attached as first term). - Clark Kimberling, Mar 12 2003

From Antti Karttunen, Oct 28 2001: (Start)

When certain Stern-Brocot tree-related permutations are conjugated with this permutation, they induce a permutation on Z (folded to N), which is an infinite siteswap permutation (see, e.g., figure 7 in the Buhler and Graham paper, which is permutation A065174). We get:

A065260(n) = a(A057115(a(n))),

A065266(n) = a(A065264(a(n))),

A065272(n) = a(A065270(a(n))),

A065278(n) = a(A065276(a(n))),

A065284(n) = a(A065282(a(n))),

A065290(n) = a(A065288(a(n))). (End)

Every nonnegative integer has a unique representation c(1) + c(2)*2 + c(3)*2^2 + c(4)*2^3 + ..., where every c(i) is 0 or 1. Taking tuples of coefficients in lexical order (i.e., 0, 1; 01,11; 001,011,101,111; ...) yields A059893. - Clark Kimberling, Mar 15 2015

From Ed Pegg Jr, Sep 09 2015: (Start)

The reduced rationals can be ordered either as the Calkin-Wilf tree A002487(n)/A002487(n+1) or the Stern-Brocot tree A007305(n+2)/A047679(n). The present sequence gives the order of matching rationals in the other sequence.

For reference, the Calkin-Wilf tree is 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, ..., which is A002487(n)/A002487(n+1).

The Stern-Brocot tree is 1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2, ..., which is A007305(n+2)/A047679(n).

There is a great little OEIS-is-useful story here. I had code for the position of fractions in the Calkin-Wilf tree. The best I had for positions of fractions in the Stern-Brocot tree was the paper "Locating terms in the Stern-Brocot tree" by Bruce Bates, Martin Bunder, Keith Tognetti. The method was opaque to me, so I used my Calkin-Wilf code on the Stern-Brocot fractions, and got A059893. And thus the problem was solved. (End)

From Trevor Green (green(AT)snoopy.usask.ca), Nov 26 2003: (Start)

a(n)/n has an accumulation point at x exactly when x is in the interval [1, 2]. Proof: Clearly n <= a(n) < 2n. Let b(n) = a(n)/n, then b(n) must always lie in [1,2) and all the accumulation points of the sequence must lie in [1,2]. We shall show that every such number is an accumulation point.

First, consider any d-bit integer n. Suppose that z of these bits are 0. Let n' be the (d+z)-bit integer whose first d bits are the same as those of n and whose remaining bits are all 1. Then a(n') will have to be the (d+z)-bit integer whose first d bits are all 1 and whose last z bits are all 0.

Thus n' = (n+1)*2^z-1; a(n') = (2^d-1)2^z; and b(n') = (2^d-1)/(n+1) + epsilon, where 0 < epsilon < 2^(1-d). So to get an accumulation point x, we just choose n(d) to be the d-bit integer such that (2^d-1)/(n(d)+1) < x <= (2^d-1)/n(d), or equivalently, n(d) = floor((2^d-1)/x). If x lies in [1,2), then n(d) will always be a d-bit number for sufficiently large d.

Then n'(d) yields an increasing subsequence of the integers for which b(n'(d)) converges to x. For x = 2, choose n(d) = 2^(d-1), which is always a d-bit number; then b(n'(d)) = (2^d-1)/(2^(d-1)+1) + epsilon = 2 + epsilon', where epsilon' also heads for 0 as d blows up. This proves the claim.

(End)

n-th row = (r(1),r(2),...,r(m)), where m=2^(n-1), satisfies r(r(k))=k for k=1,2,...,m and has exactly 2^[ n/2 ] solutions of r(k)=k. (The function r(k) reverses bits. Or rather, r(k)=revbits(k-1)+1.)

In a knockout competition with m players, arranging the competition brackets (see links) in r(k) order, where k is the rank of the player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the highest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the lowest ranked player possible is A131271. - Colin Hall, Jul 31 2011, Feb 29 2012

Row n contains one of A003407(2^(n-1)) non-averaging permutations of [2^(n-1)], i.e., a permutation of [2^(n-1)] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

a(n) is even if n is odd and a(n) is odd if n is even; this is caused by the kind of swapping the most significant and least significant binary digit when reversing n and the fact that the most significant digit of n is always 1. - R. J. Mathar, Nov 05 2015

Numbers k such that A007814(k) = A086784(k).

To reproduce the sequence through itself, use the following rule: if binary 1xyz is a term then so are 11xyz and 10xyz0 (except for 1 alone where 100 is not a term).

The number of terms with bit length k is equal to Fibonacci(k-1) for k > 1.

Conjecture: 2*A247648(n-1) + 1 with rewrite 1 -> 1, 01 -> 0 applied to binary expansion is the same as a(n) without trailing 0 bits in binary.

Odd terms are positive Mersenne numbers (A000225), because there is no 0 in their binary expansion. - Bernard Schott, Oct 12 2022

The permutation that turns a natural ordered into a sequency ordered Walsh matrix of size 2^n is the product of the Gray code permutation A003188(0..2^n-1) and the bit-reversal permutation A030109(n,0..2^n-1).

(This permutation of 2^n elements can be represented by the compression vector [2^(n-1), 3*[2^(n-2)..4,2,1]] with n elements.)

This triangle shows the compression vectors of the unique square roots of these permutations, which correspond to symmetric binary matrices with 2n-1 ones.

(These n X n matrices correspond to graphs that can be described by permutations of n elements, which are shown in A239304.)

Rows of the square array:

T(1,n) = 1,3,6,6,12,12,24,24,48,48,96,96,192,192,384,384,... (compare A003945)

T(2,n) = 1,1,9,18,18,36,36,72,72,144,144,288,288,576,576,... (compare A005010)

Columns of the square array:

T(m,1) = 1,1,5,10,10,20,20,40,40,80,80,160,160,320,320,... (compare A146523)

T(m,2) = 3,1,1,17,34,34,68,68,136,136,272,272,544,544,... (compare A110287)

This is the problem of the farmer's helper who, when asked to weigh n bags of grain, does so k at a time and reports the resulting binomial(n,k) combined weights with no indication of the k-tuples that produced them. The problem: is can the weights of the bags be recovered?

For k=3 the answer is Yes unless n is one of the four terms of this sequence. For k=2 see A057716.

The old entry with this sequence number was a duplicate of A030109.

The following references also apply to the general case of the problem.

All rows of this array are infinite permutations of the nonnegative integers. Row m (counted from 0) is always generated by modifying the sequence of nonnegative integers in the following way: The sequence of integers is written in reverse binary. Than the finite permutation p_m (row m of array A055089) is applied on the digits of all entries.

The rows of the top left n! X 2^n submatrix describe the rotations and reflections of the n-hypercube that preserve the binary digit sums of the vertex numbers. With permutation composition these permutations form the symmetric group S_n.

Applying such a permutation on the binary string of a Boolean function gives the string of a function in the same big equivalence class (compare A227723).

Triangle row m has length 2^n for m in the interval [(n-1)!,n![. The rest of the array row repeats the same pattern. The first digit of the rest is the digit before plus one.