A characterization of OEIS A393797

 In OEIS sequence A393336, the $n$-th term is the sum of positions of 1's minus sum of positions of 0's in the binary expansion of $n$. We use the convention that the position of the least significant bit is $1$ and the position of the most significant bit in an $k$-bit number is $k$. In OEIS sequence A393797, the $n$-th term $a(n)$ gives the smallest integer $w$ such that the $w$-th term of A393336 is equal to $n$. We next give a complete characterization of the sequence A393797.

Let $T_k = \frac{(k+1)k}{2} = \sum_{i=1}^k i$ denote the $k$-th triangular number.

The following observation is easily shown.

Lemma

Let $m = \sum_{i=0}^{t-1} (k-i)$. Any integer from $1$ to $m$ is the sum of a subset of at most $t$ elements of $\{1,\cdots , k\}$.

A consequence of the Lemma is that any integer from $1$ to $T_k$ is the sum of some subset of $\{1,\cdots k\}$.

Theorem

$a(n)$ is a $k$-bit number with at most two $0$'s in its binary representation. Let $k_0 = \lfloor\sqrt{2n} + \frac{1}{2}\rfloor =$ A002024$(n)$.Then $k=k_0$ if $T_k$ has the same parity as $n$, $k=k_0+1$ if $T_k$ has different parity as $n$ and $k_0$ is even, and $k=k_0+2$ if $T_k$ has different parity as $n$ and $k_0$ is odd. Let $S$ be the positions of the $0$'s in $a(n)$, i.e. $a(n) = 2^k-1-\sum_{i\in S}2^{i-1}$. Let $d = \frac{T_k-n}{2}$. Then $S = \emptyset$ if $d=0$, $S=\{d\}$ if $d<k$ and $S = \{k-1,d-k+1\}$ if $d\geq k$.

Proof

Let $a(n)$ be a $k$-bit number. First note that since there are no leading zeros, elements of $S$ is less than or equal to $k-1$. Since $n = $A393336$(a(n)) = T_k - 2\sum_{i\in S}i$ , this implies that $T_k$ and $n$ have the same parity. Note that $k_0$ is the smallest integer such that $T_{k_0}\geq n$. Since $T_k\geq n$, this implies that $k\geq k_0$. If $T_{k_0}$ has the same parity as $n$, then $k = k_0$. If $T_{k_0}$ has a different parity from $k_0$, we have $2$ cases. If $k_0$ is even, then $T_{k_0+1} = T_{k_0}+k_0+1$ and thus has a different parity from $T+{k_0}$, i.e. $T_{k_0+1}$ has the same parity as $n$ and $k = k_0+1$. If $k_0$ is odd, then $T_{k_0+2} = T_{k_0}+2k_0+3$ and thus has the same parity as $n$ and $k = k_0+2$. Thus $k$ is at most larger than $k_0$ by $2$. Note that $n>T_{k_0-1}$ and that $d =\frac{T_k-n}{2} = \sum_{i \in S} i$. Consider the case $k = k_0+2$. Then $d< \frac{T_{k_0+2}-T_{k_0-1}}{2}= \frac{3k_0+3}{2}$. The sum of the largest two elements of $\{1,...,k-1\}$ is equal to $k-1+k-2 = 2k-3$. By the above Lemma any positive integer from $1$ to $2k-3$ can be represented as the sum of at most $2$ elements of $\{1,...,k-1\}$. Next, $2k-3 = 2k_0+1\geq \frac{3k_0+3}{2}>d$. Thus $S$ has at most 2 elements. Consider the case $k = k_0$. Then $d < \frac{T_{k_0}-T_{k_0-1}}{2} = \frac{k_0}{2}$, i.e. $d\leq \lfloor\frac{k_0}{2}\rfloor \leq k_0-1$. Thus $S$ has at most $1$ element. For the case $k = k_0+1$, $d < \frac{T_{k_0+1}-T_{k_0-1}}{2} = \frac{2k_0+1}{2} = k_0+\frac{1}{2}$, i.e. $d\leq k_0$. The sum of the two largest elements of $\{1,...,k-1\}$ is equal to $2k-3 = 2k_0-1\geq k_0$. Thus $S$ has at most $2$ elements. Thus we have shown that $S$ has at most $2$ elements and thus the number of $0$'s in the binary representation of $a(n)$ is at most $2$. We can determine $S$ as follows. If $d = 0$, then $S$ is the empty set. If $d\leq k-1$, then $S = \{d\}$. Otherwise, $S = \{k-1,d-k+1\}$. Note that $k-1 \neq d-k+1$ since $d \leq 2k-3 <2k-2$ implies $k-1 > d-k+1$ .

A python program to implement this algorithm and compute the sequence A393797 efficiently can be found in the OEIS entry for A393797.