cp's OEIS Frontend

A literal interpretation of the binary numbers.

Sum of the number of digits to the left (exclusive) of each 1 in the binary expansion of n. - Gus Wiseman, Jan 09 2023

This is also "minimal subset/superset bitmask" transform of the nonnegative integers, A001477. In that transform, applicable to any N -> N injection f, we start from a(0) = 0, after which for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i for which f(k_i) is minimized; otherwise, a(n) = that h_i for which f(h_i) is minimized among the infinite set of numbers h_i for which bitand(h_i,a(n-1)) = a(n-1) and that are not yet present in the sequence. In this case f(n) = A001477(n) = n.

The original, equivalent definition is:

a(0) = 0 and for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i which gives minimum value of A019565(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by toggling a single 0-bit of a(n-1) to 1. This is done by trying to toggle successive vacant bits from the least significant end of the binary representation of a(n-1), until such a sum a(n-1) + 2^h (= a(n-1) bitxor 2^h) is found that is not already present in the sequence.

Shares with permutations like A003188, A006068, A300838, A302846, A303765 and A304083 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step.

Also, like A003188, A006068 and many other base-2 representation related permutations, this permutation preserves the binary size of n (A000523(n)), and furthermore, a(n) seems to stay at most points (except at powers of 2) remarkably close to n.

From Antti Karttunen, May 23 2018: (Start)

Outline of the proof that the definition involving A019565 is equivalent to the recurrent formula:

Even though A019565 is nonmonotonic, for example A019565(4) = 5 = p_3 < A019565(3) = 6 = p_1 * p_2, and in general, although there are always primes p_k < p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, it doesn't matter here, because not just the position of the most significant 1-bit is monotonic in this sequence (see the binary representation at A304747), but also in each subrange (2^k)+2 .. (2^(k+1))-1 the position of the second most significant 1-bit moves only leftward, i.e., is monotonic, which follows from the recursive formula.

To see this, consider the first time in this sequence when in a batch of terms (of equal binary width) we have bits in position k (the most significant position) and (k-1) on (that is, both are 1's), the latter corresponding to prime p_k: while in principle a bit-based rule could choose to subtract 2^(k-1), in preference to any 1-bits to the right of it (that correspond to primes p_{i1} .. p_{ih}), it cannot do so at this stage, because it is the second most significant 1-bit, and then it would not move only leftward, contradicting what was said above. Neither this can occur later when more 1-bits have appeared to their left: the recursive formula guarantees it.

Also conversely, even though p_4 = 7 > 6 = p_1 * p_2, and in general, we always have such prime p_k > p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, and while here A019565-based rule (see comments in A303760) would prefer dividing p_k out instead of any subset of p_{i1} .. p_{ih}, it happens that in that rule, the index of the largest prime (A061395) grows monotonically, so at the stage where p_k is the largest prime of the batch of length 2^(k-1), p_k just cannot be divided out, and also here the structure of the later batches is strictly determined by recursion.

(End)

Equals A004233(n) - 1 for n > 1.

Does not satisfy Benford's law [Whyman et al., 2016] - N. J. A. Sloane, Feb 12 2017

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)

For n >= 1, a(n) is the n-th row sum of the irregular triangle A133457. - Vladimir Shevelev, Dec 14 2015

For n >= 0, 2^a(n) is the number of partitions of n whose dimension (given by the hook-length formula) is an odd integer. See the MacDonald reference. - Arvind Ayyer, May 12 2016

One can prove by induction that n must appear in the sequence after [n/2], showing that the sequence is one-to-one; and that frac(log_2(log_2(a(n))) is dense in [0,1), from which it follows that a(n) is onto. - From Franklin T. Adams-Watters, Feb 04 2006

Comment from N. J. A. Sloane, Mar 01 2013: Although the preceding argument seems somewhat incomplete, the result is certainly true: This sequence is a permutation of the natural numbers. Mark Hennings and the United Kingdom Mathematics Trust, and (independently) Max Alekseyev, sent detailed proofs - see the link below.

The sequence consists of a series of "doubling runs", and the starting points and lengths of these runs are in A221715 and A221716 respectively. - N. J. A. Sloane, Jan 27 2013

Let's define "property S" for sequences as follows: If s is any sequence of positive natural numbers, normalized to begin with offset 1, then it satisfies the S-property if LCM-transform(s) is equal to the sequence obtained by applying A014963 to sequence s, or in other words, when for all n >= 1, lcm {s(1)..s(n)} / lcm {s(1)..s(n-1)} = A014963(s(n)). This holds if and only if, for all n >= 1, when, either (case A): s(n) is of the form p^k, p prime, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to p^(k-1), or (case B): when s(n) is not a prime power, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to s(n). Together the cases (A) and (B) reduce to the condition that each prime power should appear in s before any of its multiples do.

Clearly the Doudna-sequence satisfies the property by the way of its construction, as do many of its variants like A356867 (see A369060).

Also, for any base-2 related permutation b that keeps all the numbers of range [2^k, 2^(1+k)[ in the same range, i.e., if for all n >= 1, A000523(b(n)) = A000523(n), then the above property is automatically satisfied.

Furthermore, because in Doudna-sequence no multiple of any term is located on the same row as the term itself (see the tree-illustration in A005940), it follows that any composition of A005940 with any such base-2 related permutation as mentioned above also automatically satisfies the S-property, for example, the permutations A163511, A243353, A253563, A253565, A366260, A366263 and A366275.

Note: Like A005940 itself, also this sequence might be more logical with the starting offset 0 instead of 1, to better align with the underlying mapping from the binary expansion of n to the prime factorization. - Antti Karttunen, Jan 24 2024

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

a(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - Reinhard Zumkeller, Oct 28 2013

Empty external nodes are counted in determining the height of a search tree.