# Write $N$ as a sum of $K$ integers in a special way

$$N$$ is an integer. We need to write $$N$$ as a sum of $$K$$ integers (not necessarily distinct) such that by adding some(or all) of the integers we can get every integer in $$[1,N]$$.What is the minimum value of $$K$$?

e.g. $$N=7$$ here we can write $$7$$ as a sum of $$3$$ integers $$(1+2+4=7)$$. And...

$$1, 2, 1+2=3, 4, 4+1=5, 4+2=6, 1+2+4=7$$ every integer less than equal to $$7$$ can be expressed by adding these integers. So minimum value of $$K$$ is $$3$$.

Doing this for small integers I guessed a solution that the minimum value of $$K$$ will be the length of binary representation of $$N$$. But I am unable find why this is the case.

If $$N = 2^{I+1} -1$$ then the minimal set of you integers is $$\lbrace1,2,4,\ldots,2^I\rbrace$$. Now you are left with all cases inbetween the powers of $$2$$ ... My suspiction is that you may iteratively apply following decomposition. Lets say $$U_N$$ is the set you are looking for, then: $$U_N = \lbrace2^{I_N}\rbrace \cup U_{N-2^{I_N}}$$, where $$I_N$$ the largest number $$I$$ so that $$2^I\leq ceil(N/2)$$. Edit: see comments below this answer.
• I think if $N=2^{I+1}-1$ then minimum set will be {${{1,2,4,...,2^{I}}}$}. Isn't it? Commented Nov 9, 2018 at 9:59
• Well, you are right, something is fishy,lets see : $\sum_{i=0}^I2^i = \tfrac{1-2^{I+1}}{1-2} = 2^{I+1}-1$ ... You are correct :) Commented Nov 9, 2018 at 10:03