HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fromthedecomposingnumberrepeateddivisionsresultingtermsenumerate

Problem

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!

Solution

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

Context

StackExchange Computer Science Q#123445, answer score: 2

Revisions (0)

No revisions yet.