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

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!

• The equality $n=\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$ looks very nice. The recursive replacement and resulting sequence is interesting with a few simple interesting or intriguing propertie. This material could be used in an introductory or exploratory lesson on induction or recursion. Apr 3 '20 at 1:06

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)=$$. 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}_{-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]$$.

• This is amazing. I'll work out the code for it. Thank you very much!!! Apr 2 '20 at 14:09
• The operation, the formula, and the exercise can be similarly made for base 3, that is, splitting a term into three terms. In fact, they can be generalized to general bases. Apr 3 '20 at 1:15
• @AndreiAlexandrescu Welcome! Thanks for your interesting question! By the way, the answer to the exercise can be found at the source to my second revision Apr 3 '20 at 1:21

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$$.

• Thanks. That gets close, but results in a slightly different sequence. Consider e.g. 10 = 5 + 5 = 2 + 3 + 2 + 3 = 1 + 1 + 1 + 2 + 1 + 1 + 1 + 2. Apr 1 '20 at 12:10
• I suggest looking at few examples, trying to figure out a pattern in the location of 2s. Apr 1 '20 at 12:48