5
$\begingroup$

I got curious with the following: How can I find all the solutions for

$$\frac{1}{2^{k_1}} + \frac{1}{2^{k_2}} + \frac{1}{2^{k_3}} + \dots + \frac{1}{2^{k_n}}=1$$

for $k_i\in \Bbb{N}$ with $n$ a fixed positive integer? I thought about multiplying both sides by $2^{k_1} 2^{k_2}\dots 2^{k_n}$ but it looked useless at first sight. Is there some algorithm for that? Sorry if the question is too trivial, but I spent a while thinking and nothing came to my mind.

EDIT: I'm not sure this is actually number theory. Feel free to add or remove tags if it isn't.

$\endgroup$
  • $\begingroup$ what are $k_1, k_2, \ldots$? $\endgroup$ – gt6989b Mar 5 '19 at 19:33
  • $\begingroup$ $k_i \in \Bbb{N}$ $\endgroup$ – Billy Rubina Mar 5 '19 at 19:46
  • 1
    $\begingroup$ One solution is $k_i=i$ for $1\le i\le (n-1)$ and $k_n=k_{n-1}$. $\endgroup$ – Keith Backman Mar 5 '19 at 19:49
  • 3
    $\begingroup$ You can generate all the solutions (up to a rearrangement) by constructing the full binary trees with $n$ leaves. Then, assign values of $k_i$ to be the level of the $i$th leaf on the tree. $\endgroup$ – Theo Bendit Mar 5 '19 at 20:06
  • $\begingroup$ An interesting extension of the question is the replace the sum with a limit to infinity, where the k series would have to go through all the natural numbers. $\endgroup$ – Mikael Jensen Mar 6 '19 at 9:27
3
$\begingroup$

This image shows how to generate iteratively all solutions $(k_1, \dots, k_n)$ for all $n$, under the constraint $k_1 \le \dots \le k_n$.

enter image description here

The "sons" of every solution $(k_1, \dots , k_i, k_{i+1} \dots , k_n)$ are found by replacing $k_i$ with $(k_i+1, k_i+1)$ (under the constraint that $k_i < k_{i+1}$).

$\endgroup$
  • $\begingroup$ You missed $(1,2,4,4,4,4)$ for $n=6$ which is child of $(1,2,3,4,4)$. Also, $(1,3,3,3,4,4)$ is child of $(1,2,3,4,4)$ too. $\endgroup$ – BillyJoe Mar 7 '19 at 14:33
  • $\begingroup$ @mbjoe You are right! Thanks for your comment. I'm sorry, but I will not modify the image... $\endgroup$ – Crostul Mar 7 '19 at 18:40

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.