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!

  • $\begingroup$ 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. $\endgroup$
    – John L.
    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)=[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

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

  • $\begingroup$ This is amazing. I'll work out the code for it. Thank you very much!!! $\endgroup$ Apr 2 '20 at 14:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – John L.
    Apr 3 '20 at 1:15
  • 1
    $\begingroup$ @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 $\endgroup$
    – John L.
    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$.

  • $\begingroup$ 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. $\endgroup$ Apr 1 '20 at 12:10
  • $\begingroup$ I suggest looking at few examples, trying to figure out a pattern in the location of 2s. $\endgroup$ Apr 1 '20 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.