You are given a positive integer $n$. Find the smallest positive integer $k$, for which there exist integers $a_1, a_2, \ldots, a_k$, for which the following equality holds:
$$2^{a_1} + 2^{a_2} + \ldots + 2^{a_k} = 2^n - n + k$$
Proposed by Mykhailo Shtandenko
well, my emotional state had gotten better, lets do some NT now
We claim that the answer is $n$.
Construction is easy. starting with $2^n$ ones and merge them one by one (only merge same numbers) until there are as few as $n$ numbers.
Now note that each $2^{a_i}$ can add only a $1$ (and possibly no $1$s) to the binary representation of the sum
that is, $s_2(2^{a_1}+2^{a_2}+\dots+2^{a_k})\leq k$.
Note that if $k<n$ then the right hand side would be a $n$ digit number in binary representation. If we hope the number has $t$ zeros in the binary representation, then the number is at most $2^n-1-(2^t-1)=2^n-2^t$, which means that $k$ could at most be $n-2^t$. However, we will have $s_2(2^n-2^t)=n-t$ and $s_2(2^{a_1}+2^{a_2}+\dots+2^{a_k})\leq k=n-2^t$, which would not work for size issues.
Therefore, every $k<n$ would not work.