Permutation of the natural numbers from operation related to binary expansion of $n$

Question

• Let $$ \ell(n) = \left\lfloor\log_2 n\right\rfloor $$

• Let $T(n,k)$ be a $(k+1)$-th bit from the right side in the binary expansion of $n$. Here $$ T(n, k) = \left\lfloor\frac{n}{2^k}\right\rfloor \operatorname{mod} 2 $$

• Let $a(n)$ be a sequence of positive integers such that we start with $A:=n$ and then for $0\leqslant i\leqslant \ell(n)$ apply $A:=A + 2^iT(A,\ell(n)-i)$.

• Let $$ b(n) = \frac{a(2n)-1}{2} - n $$

I conjecture that $b(n)$ is a permutation of natural numbers such that first such that first $2^m-1$ terms are a permutation of the first $2^m-1$ natural numbers for $m\in\mathbb{N}$.

Here is the PARI/GP prog to check it numerically:

a(n) = my(L = logint(n, 2), A = n); for(i=0, L, A += 2^i*bittest(A, L-i)); A
b(n) = (a(2*n) - 1)/2 - n
test(n) = vecsort(vector(2^n-1, i, b(i))) == vector(2^n-1, i, i)

Is there a way to prove it?

Answer 1

$\ell(0)$ is problematic, so I will assume that you actually mean to restrict to positive integers rather than natural numbers.

We can rephrase the construction of $a(n)$ to emphasise the increment: let $$d_i(n) = \begin{cases} 0 & \textrm{if }i < 0 \\ d_{i-1}(n) + 2^i \, T(n + d_{i-1}(n), \ell(n) - i) & \textrm{otherwise} \end{cases}$$ Then $a(n) = n + d_{\ell(n)}(n)$ and $b(n) = \frac{d_{\ell(2n)}(2n) - 1}{2}$.

We can now convert this to a more direct recurrence for $b$. For any positive $x$, $T(x, \ell(x)) = 1$, so in general $d_0(x) = 1$. Adding $2n$ to $1$ involves no carries, so $T(2n + 1, j) = T(n, j-1)$. Then if we define $$d'_i(n) = \begin{cases} 0 & \textrm{if }i < 0 \\ d'_{i-1}(n) + 2^i \, T(n + d'_{i-1}(n), \ell(n) - i - 1) & \textrm{otherwise} \end{cases}$$ offsetting the shifts we have $$b(n) = d'_{\ell(n) - 1}(n) + 2^{\ell(n)}$$

---

At step $i$ we either add $2^i$ or we don't, so $d'_i(n)$ can be viewed as a set of powers of 2 corresponding to its binary representation. In particular this means that $0 \le d'_i(n) < 2^{i+1}$, so $2^{\ell(n)} \le b(n) < 2^{\ell(n)+1}$, giving the desired property that it maps $[2^m, 2^{m+1})$ to $[2^m, 2^{m+1})$.

---

Suppose $b(2^m + j) = b(2^m + k)$ where wlog $0 \le j < k < 2^m$. Then $d'_{m-1}(2^m + j) = d'_{m-1}(2^m + k)$. Let this value be $D$.

Because of the previously noted binary construction of $d'_i(n)$, this means that $\forall i < m: d'_i(2^m + j) = d'_i(2^m + k) = D \bmod {2^{i+1}}$ and we obtain $$\forall i \in [0,m): T(2^m + j + (D \bmod {2^{i+1}}), m - i - 1) = T(2^m + k + (D \bmod {2^{i+1}}), m - i - 1)$$ $2^m$ is too high to be relevant to these bit extractions, so $$\forall i \in [0,m): T(j + (D \bmod {2^{i+1}}), m - i - 1) = T(k + (D \bmod {2^{i+1}}), m - i - 1)$$ We can now proceed by induction on $i$ from $i=m-1$ down to $i=0$ to show that $j = k$, deriving a contradiction and demonstrating that $b$ does indeed permute the positive integers.