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.
$\endgroup$ 12 Answers
$\begingroup$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}$.
$\endgroup$ $\begingroup$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$.
$\endgroup$
