Largest subset with no pair summing to power of two 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.
 A: 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}$.
A: 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$. 
A: 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$.
