For positive integer $n$, define the set $A_n=\{0,1,\ldots,n\}$. What is the size of the largest subset of $A_n$ such that the sum of any two (not necessarily distinct) elements in it is not a power of $2$?
So, a power of $2$ can never be chosen. For $n=3,4,5$, the set $\{0,3\}$ is the best possible, and for $n=6,7$ we can choose $\{0,3,6\}$ and $\{0,3,6,7\}$, respectively.
On
The first $38$ entries in this sequence are, if I haven't made any mistakes, $$ \eqalign{a(0) &= 1\cr a(1) &= 1\cr a(2) &= 1\cr a(3) &= 2\cr a(4) &= 2\cr a(5) &= 2\cr a(6) &= 3\cr a(7) &= 4\cr a(8) &= 4\cr a(9) &= 4\cr a(10) &= 4\cr a(11) &= 5\cr a(12) &= 6\cr a(13) &= 6\cr a(14) &= 7\cr a(15) &= 8\cr a(16) &= 8\cr a(17) &= 8\cr a(18) &= 8\cr a(19) &= 9\cr a(20) &= 9\cr a(21) &= 9\cr a(22) &= 10\cr a(23) &= 11\cr a(24) &= 12\cr a(25) &= 12\cr a(26) &= 12\cr a(27) &= 13\cr a(28) &= 14\cr a(29) &= 14\cr a(30) &= 15\cr a(31) &= 16\cr a(32) &= 16\cr a(33) &= 16\cr a(34) &= 16\cr a(35) &= 17\cr a(36) &= 17\cr a(37) &= 17\cr }$$ The sequence does not seem to be in the OEIS. It appears that $a(n)$ is not far from $n/2$.
On
Suppose we can pick a good subset $S$ of size $a(n)$ from $A_n$. Then from $A_{2n}$, we can pick the $\lfloor n/2\rfloor$ number $\equiv 3\pmod 4$ and the $a(n)$ numbers $2S$: Adding two of the latter kind cannot give a power of two, adding two of the first kind gives a number $\equiv 2\pmod4>2$ , and a mixed sum is odd (and $\ne1$). We conclude $a(2n)\ge a(n)+\lfloor n/2\rfloor$. Suppose we know $a(n)\ge u n +v$. Then $a(2n+1)\ge a(2n)\ge (u+\tfrac12)n+v-\tfrac12$ and we can conclude that also $a(2n+1)\ge u(2n+1)+v$ provided $(u-\frac12)n\le -\frac12-v$. One way to achieve this is to have $v=\frac12$ and $u\le\frac12$.
By picking the maximal $u$ for $n=8,\ldots,15$, we obtain the bound $$a(n)\ge 0.35 n+\frac12$$ for all $n\ge8$. By using later values as a starting point, we can certainly achieve larger values of $u$, likely way closer to $\frac12$.
On
Let n be a positive integer and denote $r=2^{\lfloor \log_2(n)\rfloor+1}-n$. Note that $0<r\leq 2^{\lfloor \log_2(n)\rfloor}\leq n<2^{\lfloor \log_2(n)\rfloor+1}$. Then we will prove that $a(n)=2^{\lfloor\log_2(n)\rfloor}-r+a(r-1)$.
First consider the case where $n=2^k$. Any set of integers avoiding powers of $2$ in $[0,2^k]$ cannot contain $2^k$ so it is contained in $[0,2^k-1]$ and any set of integers in $[0,2^k-1]$ is contained in $[0,2^k]$. So $a(2^k)=a(2^k-1)$. As $n=2^k$, we have $r=2^{k+1}-2^k=2^k$ and $$2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)=2^k-2^k+a(2^k-1)=a(2^k-1)=a(2^k)=a(n)$$ Therefore the equation holds for powers of $2$.
Now assume $n$ is not a power of $2$. We prove that $a(n)\geq2^{\lfloor\log_2(n)\rfloor}-r+a(r-1)$. Let $T$ be a subset of $[0,r-1]$ of size $a(r-1)$ that does not contain integers that sum to a power of $2$ and that avoids powers of $2$. Then let $$A=T\cup[2^{\lfloor \log_2(n)\rfloor}+1,n]$$ Note that as $n=2^{\lfloor \log_2(n)\rfloor+1}-r$, and $T\cap[2^{\lfloor \log_2(n)\rfloor}+1,n]$ is empty as $r-1<2^{\lfloor \log_2(n)\rfloor}+1$ , $$|A|=2^{\lfloor\log_2(n)\rfloor}-r+a(r-1)$$
The sum, $S$, of any two integers in $[2^{\lfloor \log_2(n)\rfloor}+1,n]$ is $$2^{\lfloor \log_2(n)\rfloor+1}+1<S\leq 2n<2^{\lfloor \log_2(n)\rfloor+2}$$ so $S$ cannot be a power of $2$. Clearly $[2^{\lfloor \log_2(n)\rfloor}+1,n]$ does not contain a power of $2$. Any integer, $t$, in $T$ is $0\leq t<r$ and any integer, m, in $[2^{\lfloor \log_2(n)\rfloor}+1,n]$ is $2^{\lfloor \log_2(n)\rfloor}+1\leq m\leq 2^{\lfloor \log_2(n)\rfloor+1}-r$ so $$2^{\lfloor \log_2(n)\rfloor}+1\leq t+m < 2^{\lfloor \log_2(n)\rfloor+1}$$ Therefore $t+m$ cannot equal a power of $2$.
So $a(n)\geq 2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)$.
To prove the reverse inequality, assume that $a(n)\geq 2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)+1$, i.e. that there exists a subset of $[0,n]$, $A$, that does not contain any $2$ integers that sum to a power of $2$ and that does not contain any powers of $2$ where $A$ is of size $2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)+1$.
Then there are at most $a(r-1)$ integers in $A\cap[0,r-1]$, so there are at least $2^{\lfloor \log_2(n)\rfloor}-r+1$ integers in $A\cap[r,n]$. As $A$ avoids powers of $2$, there must be at least $2^{\lfloor \log_2(n)\rfloor}-r+1$ integers in $$A\cap([r,2^{\lfloor \log_2(n)\rfloor}-1]\cup[2^{\lfloor \log_2(n)\rfloor}+1,n])$$ $$=A\cap([2^{\lfloor \log_2(n)\rfloor}-(2^{\lfloor \log_2(n)\rfloor}-r),2^{\lfloor \log_2(n)\rfloor}-1]\cup[2^{\lfloor \log_2(n)\rfloor}+1,2^{\lfloor \log_2(n)\rfloor}+(2^{\lfloor \log_2(n)\rfloor}-r)])$$ Note that $|[r,2^{\lfloor \log_2(n)\rfloor}-1]|=2^{\lfloor \log_2(n)\rfloor}-r=n-2^{\lfloor \log_2(n)\rfloor}=|[2^{\lfloor \log_2(n)\rfloor}+1,n]|$.
$2^{\lfloor \log_2(n)\rfloor}-k$ is an integer in $[r,2^{\lfloor \log_2(n)\rfloor}-1]$ if and only if $2^{\lfloor \log_2(n)\rfloor}+k$ is an integer in $[2^{\lfloor \log_2(n)\rfloor}+1,n]$ and as $2^{\lfloor \log_2(n)\rfloor}-k+2^{\lfloor \log_2(n)\rfloor}+k=2^{\lfloor \log_2(n)\rfloor+1}$, only one of these integers can be in $A$. So at most half the integers in $[r,2^{\lfloor \log_2(n)\rfloor}-1]\cup[2^{\lfloor \log_2(n)\rfloor}+1,n]$ can be in $A$. Therefore at most $2^{\lfloor \log_2(n)\rfloor}-r$ integers are in $A\cap([r,2^{\lfloor \log_2(n)\rfloor}-1]\cup[2^{\lfloor \log_2(n)\rfloor}+1,n])$. However this is a contradiction as we previously noted that there would need to be at least one more integer in this set.
Therefore $a(n)<2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)+1$ and so $a(n)=2^{\lfloor \log_2(n)\rfloor}-r+a(r-1)$.
This could also be written as $a(n)=n-2^{\lfloor \log_2(n)\rfloor}+a(2^{\lfloor \log_2(n)\rfloor+1}-n-1)$.
Applying this repeatedly gives us a useful algorithm to calculate $a(n)$ in at most $\log_2(n)$ steps as $2^{\lfloor\log_2(r-1)\rfloor}\leq r-1<2^{\lfloor\log_2(n)\rfloor}$. We use this to prove many of the following results.
This equation with a similar argument to the above can be used to show that the greedy algorithm (going from $0$ to $n$ and adding the next integer to the set iff it is not a power of $2$ and does not sum to a power of $2$ with an integer already in the set) always provides a set of largest possible size. This is done using strong induction on $n$. The base cases are simple to verify and then we want to prove this for $n$, assuming it holds for all positive integers less than $n$. We say that by the inductive hypothesis the set of size $a(r-1)$ in $[0,r-1]$ is built using the greedy algorithm. Letting $p$ be the number of integers the algorithm adds to the set from $[r,2^{\lfloor\log_2(n)\rfloor}-1]$ we see that the algorithm then adds all but $p$ integers from $[2^{\lfloor\log_2(n)\rfloor}+1,n]$ by the reasoning in the above proof. This gives the set of the required size. (This proof works for $n=2^k$ as well but stops after the set of size $a(r-1)$ as this is a set of size $a(2^k-1)=2^{k-1}=a(2^k)$ and both $[r,2^{\lfloor\log_2(n)\rfloor}-1]$ and $[2^{\lfloor\log_2(n)\rfloor}+1,n]$ are empty).
It is then clear that an integer, $t$, is in the set constructed by the greedy algorithm iff $a(t-1)<a(t)$. From this we can use the recursive formula proved above to say that $2^k-1$ and $2^k+3$ are in the set and $2^k,2^k+1,2^k+2$ are not. Note that when applying the greedy algorithm, t is in the set iff $t$ is not a power of $2$ and $2^{\lfloor\log_2(t)\rfloor+1}-t<2^{\lfloor\log_2(t)\rfloor}$ is not already in the set. Similarly, $t$ is not in the set iff $t$ is a power of $2$ or $2^{\lfloor\log_2(t)\rfloor+1}-t<2^{\lfloor\log_2(t)\rfloor}$ is already in the set. Assume that $4$ consecutive integers are in the set and let $a,a+1,a+2,a+3$ be the minimal such integers. So $a,a+1,a+2,a+3$, are in the set iff $4$ consecutive integers $b,b+1,b+2,b+3$ are not in the set. Let $2^k<a,a+1,a+2,a+3<2^{k+1}$ so we know $b,b+1,b+2,b+3<2^k$. We know none of $b,b+1,b+2,b+3$ can be powers of $2$ as $2^k-1$ and $2^k+3$ are in the set. So $b,b+1,b+2,b+3$ are not in the set iff $c,c+1,c+2,c+3$ are in the set and $c+3<2^{\lfloor\log_2(b)\rfloor}$. But this contradicts the minimality of $a$. So there are no $4$ consecutive integers in the set constructed by the greedy algorithm. Similarly there are no $4$ consecutive integers not in the set.
The recursive formula that was proved can be applied to find solutions to numbers of a general form not just specific values, eg for $0\leq c<2^{k-1}$ $$a(2^k+c)=2^k-(2^k-c)+a(2^k-c-1)=c+a(2^k-c-1)$$ $$=c+(2^{k-1}-(c+1)+a(c))=2^{k-1}-1+a(c)$$ and $0< c\leq 2^{k-1}$ $$a(2^k-c)=2^{k-1}-c+a(c-1)$$ Note that all numbers can be written in one of these forms. Using these, for a fixed $c$, finding $a(c)$ gives you $a(2^k+c)$ for all $k>\log_2(c)$ and finding $a(c-1)$ gives you $a(2^k-c)$ for all $k\geq \log_2(c)+1$. For instance $a(5)=2$ means $a(2^k+5)=2^{k-1}+1$ for $k\geq 3$ and $a(2^k-6)=2^{k-1}-4$ for all $k\geq 4$.
The recursive formula can be rewritten as $a(n)=\frac{n}{2}+a(r-1)-\frac{r}{2}$ and using the fact that $a(n)\leq \left\lceil \frac{n}{2}\right\rceil$ for all $n\geq 1$, (Representing Powers Of $2$ By A Sum Of Four Integers, Combinatorica 16 (3)(1996)413-416, V. LEV as Erick Wong mentioned), we see that $a(n)\leq \frac{n}{2}$ if $r-1>0$. If $r-1=0$ (ie $r=1$) then $a(n)=\frac{n+1}{2}$ and so $a(n)=\frac{n+1}{2}$ iff $r-1=0$. As $r=1$ iff $n=2^k-1$, $a(n)=\frac{n+1}{2}$ iff $n=2^k-1$ for some positive integer $k$. This can then be used to show that $a(n)=\frac{n}{2}$ iff $n>0$ is a difference of two positive powers of $2$. This is because we must have $a(r-1)=\frac{r}{2}=\frac{(r-1)+1}{2}$ so $r-1=2^l-1$ for some positive integer $l\leq\lfloor\log_2(n)\rfloor$ and $n=2^{\lfloor\log_2(n)\rfloor+1}-2^l$. It can be seen that whenever $n>0$ is the difference of two powers of $2$, the larger one must be $2^{\lfloor\log_2(n)\rfloor+1}$ as otherwise the difference would be too large. So $a(n)=\left\lceil \frac{n}{2}\right\rceil$ iff $n>0$ is a difference of two powers of $2$ (as $2^k-1=2^k-2^0$).
Letting $n_1=2^k+1$ for $k\geq 1$ we see that $a(n_1)=2^{k-1}=\frac{n_1-1}{2}$. Then if $a(n_{i-1})=\frac{n_{i-1}-c}{2}$, we choose $n_i$ to equal $2^{k+1}-n_{i-1}-1$ for any $k\geq \log_2(n_{i-1}+1)$, and we get that $a(n_i)=\frac{n_i}{2}+a(n_{i-1})-\frac{n_{i-1}+1}{2}=\frac{n_i-(c+1)}{2}$. We find that $a(n_i)=\frac{n_i}{2}-\frac{i}{2}$ which together with $a(2^l-1)=\frac{n+1}{2}$ and $a(2^l)=\frac{n}{2}$ shows that for every integer $c\geq-1$, there are infinitely many $n$ such that $a(n)=\frac{n-c}{2}$.
Now let $n_{i+1}=2^{\lfloor \log_2(n_i)\rfloor+1}-n_i-1$ where $0\leq n_{i+1}< 2^{\lfloor \log_2(n_i)\rfloor}$. So $a(n_1)=\frac{n_1}{2}+a(n_2)-\frac{n_2+1}{2}$. Then we have $a(n_1)-\frac{n_1}{2}+\frac{1}{2}=a(n_2)-\frac{n_2}{2}$ and iterating this, we get $$a(n_1)-\frac{n_1}{2}+(s-1)\times\frac{1}{2}=a(n_2)-\frac{n_2}{2}+(s-2)\times\frac{1}{2}=\ldots=a(n_s)-\frac{n_s}{2}$$ But for some $s\leq \lfloor \log_2(n_1)\rfloor+1$, $0\leq n_s<2$ so $a(n_s)-\frac{n_s}{2}\geq \frac{1}{2}$. Therefore $$a(n_1)-\frac{n_1}{2}+(\lfloor \log_2(n_1)\rfloor)\times\frac{1}{2}\geq a(n_1)-\frac{n_1}{2}+(s-1)\times\frac{1}{2}\geq \frac{1}{2}$$ and so $$a(n_1)\geq\frac{n_1+1}{2}-\frac{\lfloor \log_2(n_1)\rfloor}{2}$$ So we have that $$a(n)\geq\frac{n+1}{2}-\frac{\lfloor \log_2(n)\rfloor}{2}$$ for all $n>0$. Considering that we have $$\frac{n+1}{2}-\frac{\lfloor \log_2(n)\rfloor}{2}\leq a(n)\leq\frac{n+1}{2}$$ it follows that $$\lim_{n\to\infty}\frac{a(n)}{n}=\frac{1}{2}$$
This lower bound is tight as we can take an $n'>1$ such that $a(n')=\frac{n'+1}{2}-\frac{\lfloor \log_2(n')\rfloor}{2}$, eg $n'=42$, and then take $n=2^{\lfloor\log_2(n')\rfloor+2}-n'-1$. Note that $n'$ is not one less than a power of $2$ as from above this would imply that $a(n')>\frac{n'}{2}$. Therefore $n'+1<2^{\lfloor\log_2(n')\rfloor+1}$, so $2^{\lfloor\log_2(n')\rfloor+2}$ is the smallest power of $2$ greater than $n$. This implies $2^{\lfloor\log_2(n')\rfloor+2}=2^{\lfloor\log_2(n)\rfloor+1}$ and $\lfloor\log_2(n')\rfloor+1=\lfloor\log_2(n)\rfloor$. Then $$a(n)=\frac{n}{2}+a(n')-\frac{n'+1}{2}=\frac{n}{2}+\frac{n'+1}{2}-\frac{\lfloor \log_2(n')\rfloor}{2}-\frac{n'+1}{2}=\frac{n}{2}-\frac{\lfloor \log_2(n')\rfloor}{2}$$ $$=\frac{n}{2}-\frac{\lfloor\log_2(n)\rfloor-1}{2}=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$$
As $n'<2^{\lfloor\log_2(n')\rfloor+1}=2^{\lfloor\log_2(n)\rfloor}\leq n$ we can use this to construct infinitely many $n$ such that $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$.
We can inductively prove that for $n=\left\lfloor \frac{2^k}{3}\right\rfloor$, $k\geq2$, we have $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$. The base cases for $k=2,3$ gives $n=1,2$ and clearly satisfies the equation. Then we assume $n=\left\lfloor \frac{2^{k-1}}{3}\right\rfloor$ satisfies $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$. We split the inductive step into the case that $k$ is odd and $k$ is even. If $k$ is odd then $n=\left\lfloor \frac{2^{k-1}}{3}\right\rfloor=\frac{2^{k-1}-1}{3}$ and $a\left(\frac{2^{k-1}-1}{3}\right)=a\left(\frac{2^{k-1}+2}{3}-1\right)$. Note that $$\left\lfloor\frac{2^k}{3}\right\rfloor=\frac{2^k-2}{3}=2^{k-1}-\frac{2^{k-1}+2}{3}$$ So $$a\left(\frac{2^k-2}{3}\right)=\frac{2^{k-1}-1}{3}+a\left(\frac{2^{k-1}+2}{3}-1\right)-\frac{2^{k-2}+1}{3}$$ $$=\frac{2^{k-2}-2}{3}+\frac{2^{k-2}+1}{3}-\frac{k-3}{2}=\frac{2^k+1}{6}-\frac{k-2}{2}=\frac{\frac{2^k-2}{3}+1}{2}-\frac{\left\lfloor\log_2(\frac{2^k-2}{3})\right\rfloor}{2}$$ So $\frac{2^k-2}{3}=\left\lfloor\frac{2^k}{3}\right\rfloor$ satisfies the desired equation when $k$ is odd. The case when $k$ is even follows from an identical argument. So the induction is complete.
Now consider $n>0$ such that $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$. We also know that $a(n)=\frac{n}{2}+a(r-1)-\frac{r}{2}$ so $$\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}=\frac{n}{2}+a(r-1)-\frac{r}{2}$$ and therefore $a(r-1)=\frac{r}{2}-\frac{\lfloor\log_2(n)\rfloor-1}{2}$. Note that we know that $$a(r-1)\geq \frac{(r-1)+1}{2}-\frac{\lfloor\log_2(r-1)\rfloor}{2}=\frac{r}{2}-\frac{\lfloor\log_2(r-1)\rfloor}{2}$$ So $$\frac{r}{2}-\frac{\lfloor\log_2(n)\rfloor-1}{2}\geq\frac{r}{2}-\frac{\lfloor\log_2(r-1)\rfloor}{2}$$ Therefore $\lfloor\log_2(n)\rfloor-1\leq\lfloor\log_2(r-1)\rfloor$. However we know that $$2^{\lfloor\log_2(r-1)\rfloor}\leq r-1<2^{\lfloor\log_2(n)\rfloor}$$ and so $\lfloor\log_2(r-1)\rfloor<\lfloor\log_2(n)\rfloor$. So $\lfloor\log_2(n)\rfloor-1=\lfloor\log_2(r-1)\rfloor$. Then $$a(r-1)=\frac{(r-1)+1}{2}-\frac{\lfloor\log_2(r-1)\rfloor}{2}$$ and therefore if $n$ satisfies $$a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$$ so does $r-1$. Let $n_1=n$ and $n_2=r_1-1$ where $r_i=2^{\lfloor\log_2(n_i)\rfloor+1}-n_i$. We can keep iterating this with $n_{i+1}=r_i-1$ and as $\lfloor\log_2(n_{i+1})\rfloor=\lfloor\log_2(r_i-1)\rfloor=\lfloor\log_2(n_i)\rfloor-1$, eventually this chain leads to $\lfloor\log_2(n_{s})\rfloor=0$ for some $s$. So $1=n_s=r_{s-1}-1$ and therefore $r_{s-1}=2$. So $\lfloor\log_2(r_{s-1}-1)\rfloor=\lfloor\log_2(n_{s-1})\rfloor-1$ implies that $\lfloor\log_2(n_{s-1})\rfloor=1$ and so $n_{s-1}=2^2-2=2$. Note that $n_s=1=\left\lfloor\frac{2^2}{3}\right\rfloor$ and $n_{s-1}=2=\left\lfloor\frac{2^3}{3}\right\rfloor$. We will show that if $n_{i+1}=\left\lfloor\frac{2^k}{3}\right\rfloor$ then $n_i=\left\lfloor\frac{2^{k+1}}{3}\right\rfloor$ and thus show that $n=n_1=\left\lfloor\frac{2^l}{3}\right\rfloor$ so all the positive integers such that $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$ are of the form $\left\lfloor\frac{2^t}{3}\right\rfloor$. So let $n_{i+1}=\left\lfloor\frac{2^k}{3}\right\rfloor$. Then $r_i-1 =\left\lfloor\frac{2^k}{3}\right\rfloor$ and $\lfloor\log_2(n_i)\rfloor=\lfloor\log_2(r_i-1)\rfloor+1=k-1$. So $n_i=2^{\lfloor\log_2(n_i)\rfloor+1}-r_i=2^k-\left\lfloor\frac{2^k}{3}\right\rfloor-1$. If $k$ is odd then $n_i=2^k-\frac{2^k+1}{3}=\frac{2^{k+1}-1}{3}=\left\lfloor\frac{2^{k+1}}{3}\right\rfloor$ and if $k$ is even then $n_i=2^k-\frac{2^k+2}{3}=\frac{2^{k+1}-2}{3}=\left\lfloor\frac{2^{k+1}}{3}\right\rfloor$. So $a(n)=\frac{n+1}{2}-\frac{\lfloor\log_2(n)\rfloor}{2}$ iff $n=\left\lfloor\frac{2^l}{3}\right\rfloor$ for $l\geq 2$.
So the final bounds we achieve are $$\frac{n+1}{2}-\frac{\lfloor \log_2(n)\rfloor}{2}\leq a(n)\leq \frac{n+1}{2}$$ or $$\frac{n+1}{2}-\frac{\lfloor \log_2(n)\rfloor}{2}\leq a(n)\leq \left\lceil\frac{n}{2}\right\rceil$$ for $n>0$ and the upper and lower bounds are attained for infinitely many $n$ where we have characterised exactly which $n$ achieve these bounds.
This is a partial solution. Nevertheless, I hope it helps somehow.
Consider the same problem, but now $A_n=\{1,\ldots,n\}$. We always can add $0$ at the end.
I have a solution when $n$ is itself a power of two, say $n=2^k$. A set in this case is $$2^{k-1}+1,2^{k-1}+2,\ldots,2^k-1$$
The sum of two of these numbers is $\ge2(2^{k-1}+1)=2^k+2>2^k$ and $\le 2(2^k-1)=2^{k+1}-2<2^{k+1}$. So never is a power of two. But in this set there are $$2^{k-1}-1$$ numbers. Let's show that this is the greatest possible size.
If there is a set with $2^{k.-1}$ elements, then at least one of them, say $a_1$, is lesser than $2^{k-1}$. But then, $2^k-a_1$ can not be in the set. Therefore, there must be another element $a_2$ lesser than $2^{k-1}$, etc.
We conclude that every element is lesser than $2^{k-1}$, a contradiction.
Now we can add the number $0$, so the solution is $2^{k-1}$.