Enumerate the terms resulting from decomposing a number by repeated divisions by 2

Question

Consider a natural number $n>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = 4 + 5 = 2 + 2 + 2 + 3 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2$.

There will be $2^{\lfloor \log_2 n\rfloor}$ terms because the decomposition forms a complete binary tree of height $\lfloor \log_2 n\rfloor$.

I am looking for an iterative form of this recursive process. The enumeration $a_0 = 0, a_{i+1} = \left\lfloor \frac {(i+1) \cdot n} {2^{\lfloor \log_2 n\rfloor}} \right\rfloor - a_i$ comes close because it does satisfy the following conditions: (a) each term is 1 or 2; (b) the sum of the first $2^{\lfloor \log_2 n\rfloor}$ terms is $n$. But the elements are not identical to the recursive decomposition form.

Any help would be welcome. Thanks!

Answer 1

Let $2^m$ be the largest power of $2$ not greater than $n$, a positive integer.

As mentioned in the question, if we repeatedly replace each term $\cdot$ with $\lfloor \frac \cdot2 \rfloor$, $\lceil \frac \cdot2 \rceil$, we will change $[n]$ to a sequence of $2^m$ terms, each of which is either 1 or 2.

Let that sequence be $S(n)=[S_0, S_1, S_2,\cdots, S_{2^m-1}]$. We have $S_0=1$ since $S_0=\lfloor\frac n{2^m}\rfloor$.

Formula for the general term. For all $i$, we have $S_i=1$ if $n-2^m \le r\!c_m(i)$ and $S_i=2$ otherwise.

Here $r\!c_m(i)$ is the reverse of the complement of $m$-bit binary representation of $i$, i.e, if the binary representation of $i$ is $i_{m-1}i_{m-2}\cdots i_1i_0$, then the binary representation of $r\!c_m(i)$ is $(1-i_0)(1-i_1)\cdots(1-i_{m-2})(1-i_{m-1})$ .

For example, we have $$[r\!c_3(0), r\!c_3(1), r\!c_3(2), r\!c_3(3), r\!c_3(4), r\!c_3(5), r\!c_3(6), r\!c_3(7)]=[7, 3, 5, 1, 6, 2, 4, 0].$$ Since $12 = 2^3 + 4$, comparing 4 with each term $r\!c_3(\cdot)$, we obtain,

$$S(12) = [1,2,1,2,1,2,1,2].$$

Proof: We do induction on $m$, which is $\lfloor\log_2(n)\rfloor$.

The base case is when $m=0$, i.e., $n=1$. The sequence $S(1)=[1]$. The formula holds.

Suppose the formula is true for $m$, i.e, for all $n$ and $i$ such that $2^m\le n\lt2^{m+1}$, $S(n)_i=1$ iff $n-2^m\le r\!c_m(i)$.

Now consider the case of $m+1$.

Suppose $2^{m+1}\le n\lt2^{m+2}$. By definition, we have $S(n)=[S(\lfloor \frac n2 \rfloor), S(\lceil \frac n2 \rceil)]$, where we abuse the bracket so that $[\cdot, \cdot]$ means the concatenation of the two sequence, i.e., for example, $[[1,2,2,1], [1,1,1,2]]=[1,2,2,1,1,1,1,2]$. Since $2^m\le\lfloor \frac n2 \rfloor, \lceil \frac n2 \rceil\lt2^{m+1}$, we can apply the induction hypothesis to $S(\lfloor \frac n2 \rfloor)$ and $S(\lceil \frac n2 \rceil)$.

What is $S(n)_i$? There are two cases.

• $0\le i\lt 2^m$. Then $S(n)_i = S(\lfloor \frac n2 \rfloor)_i$. So $$\begin{align} S(n)_i=1&\Leftrightarrow S(\lfloor \frac n2 \rfloor)_i=1 \\&\Leftrightarrow \lfloor \frac n2 \rfloor-2^m\le r\!c_m(i) \\&\Leftrightarrow 2(\lfloor \frac n2 \rfloor-2^m)\le 2r\!c_m(i) \\&\Leftrightarrow n -2^{m+1}\le r\!c_{m+1}(i) \end{align}$$ where the last equivalence comes from the fact $2\lfloor \frac n2 \rfloor$ equals $n$ or $n-1$ and $2r\!c_m(i)=r\!c_{m+1}(i)-1$.
• $2^m\le i\lt2^{m+1}$. Then $S(n)_i = S(\lceil \frac n2 \rceil)_{i-2^m}$. So $$\begin{align} S(n)_i=1&\Leftrightarrow S(\lceil \frac n2 \rceil)_{i-2^m}=1 \\&\Leftrightarrow \lceil \frac n2 \rceil-2^m\le r\!c_m({i-2^m}) \\&\Leftrightarrow 2(\lceil \frac n2 \rceil-2^m)\le 2r\!c_m({i-2^m}) \\&\Leftrightarrow n -2^{m+1}\le r\!c_{m+1}(i) \end{align}$$ where the last equivalence comes from the fact $2\lceil \frac n2 \rceil$ equals $n$ or $n+1$ and $2r\!c_m({i-2^m})=r\!c_{m+1}(i)$.

---

Once we know the above formula, we have the following simple iterative algorithm, which is a direct translation of the formula above.

Input: a positive integer $n$.
Output: the wanted sequence
Procedure:

1. Compute integer $m$ and $n_r$ such that $n=2^m+n_r$, where $0\le n_r\lt 2^m$.

2. loop $i$ through 0 to $2^m-1$.

   1. Compute the reverse of the $m$-bit complement of $i$, $rc_m(i)$.
   2. Output $1$ if $n_r \le rc_m(i)$. Output 2 otherwise.

Note that for $i$ between $0$ and $2^m-1$, the function $i\to rc(i)$ is a bijective function, since both complement and reverse are bijective. We could optimize the algorithm by devising a way to compute the binary representation of $rc(i+1)$ directly from the binary representation of $rc(i)$. That will make the algorithm even more "iterative" as well. We can also precompute the sequence $r\!c_m(0), r\!c_m(1), \cdots, r\!c_m(2^m-1)$ by taking advantage of its iterative pattern, for example, with $m=4$, $$15, \underbrace{7}_{[15]-8}, \underbrace{11, 3}_{[15,7]-4}, \underbrace{13, 5, 9, 1}_{[15, 7, 11, 3]-2}, \underbrace{14, 6, 10, 2, 12, 4, 8, 2}_{[15, 7, 11, 3, 13, 5, 11, 1]-1}.$$

---

A simple exercise. Find the similar formula for the general sequence $S_k(n)$, which is obtained by modifying the sequence $[n]$ for $k$ rounds, where every term $\cdot$ in the sequence is replaced by two terms, $\lfloor \frac \cdot2 \rfloor$ and $\lceil \frac \cdot2 \rceil$ in each round. $n$ and $k$ can be any nonnegative integer. For example, $S_2(10)=[2, 3, 2, 3]$ and $S_4(10)=[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1]$.

Answer 2

Denote the total number of terms by $m = 2^{\lfloor \log n \rfloor}$. Suppose that $m_1$ terms are equal to $1$, and $m_2$ terms are equal to $2$. Thus $$ n = m_1 + 2m_2 = m + m_2, $$ from which we find that $m_2 = n-m$ and $m_1 = 2m-n$. So if you arrange the terms in nondecreasing order, the first $2m-n$ would be $1$, and the remaining $n-m$ would be $2$.