Greatest possible cardinality of a set of numbers less than 1000 such that the sums avoid powers of 2

Question

Let $S = \{1, 2, \dotsc, 1000\}$, $T$ is a subset of $S$. For any $a, b\in T$ (can be the same), $a + b$ is not a power of $2$. Find the greatest possible value of $|T|$.

Notice that if $a+a=2^N=2a$, then $a$ must be a power of $2$ as well. Namely $2^{N-1}$. Hence we can't include any power of 2 in the set of $T$ as $a$ and $b$ could be the same.

That leaves us for $T=\{1,3,5,6,...,513,514,...,1000\}$. Now notice that if $1+b=2^N$, then $b=2^N-1$, which means every number such that it is one less than a power of $2$ can't be included inside, or $1$ could not be inside.

Similar for $3, 5, 6, \dotsc$ as a number with $1, 3, 5, \dotsc$ less than a power of $2$ is much more than a single number $1, 3, 5$ etc. Hence I think it would be more clever to exclude the single number $1, 3, 5, \dotsc$ (I don't know if it's right).

From here on I'm stuck and I have no idea.

Answer 1

For any $n\in\mathbb N$, let $h(n)$ mean the distance from $n$ up to the next power of $2$ -- that is, in symbols, $$ h(n) = 2^{\lfloor 1+\log_2 n\rfloor} - n $$ It is easy to see that if $a+b$ is a power of $2$ and $a\le b$, then $a=h(b)$. Therefore, the condition of $T$ is equivalent to saying that $T$ does not contain both $b$ and $h(b)$ for any $b$, or in yet other words $T\cap h(T)=\varnothing$.

Let $S^*$ be $S\setminus h(S)$, the elements of $S$ that are not hit by $h$. These elements are "gratis" to add to $T$ in the sense that if $T_1$ satisfies the condition, then $$ T_2 = \bigl(T_1 \setminus h(S^*)\bigr) \cup S^* $$ will be another qualifying $T$, and in addition $T_2$ that has at least as many elements as $T_1$. Namely, each element of $h(S^*)$ that was in $T_1$ but is removed corresponds to at least one element of $S^*$ that is added.

Therefore, we can assume without loss of generality that a $T$ of maximal size contains $S^*$.

For $S=\{1,2,3,\ldots,1000\}$, we have $S^*=\{513,514,\ldots,1000\}$, so these $488$ elements are certainly in $T$. And $h(S^*)=\{24,25,\ldots,511\}$ so these elements cannot be in our $T$. Neither can $512$, of course, being a power of $2$ itself.

So all we have to do now is to supplement with as many elements of $S_2=\{1,2,3,\ldots,23\}$ as we can. But that's just a smaller instance of the problem we're already solving, so we can proceed recursively:

$$ S_2^* = \{17,18,\ldots,23\} \\ h(S_2^*) = \{9,10,\ldots,15\} \\ S_3 = \{1,2,\ldots,7\} $$ (ignoring $8$ which is a power of $2$) $$ S_3^* = \{5,6,7\} \\ h(S_3^*) = \{1,2,3\} $$ at which point we have exhausted the entire original $S$. Therefore, a $T$ with maximal size is $$ \{5,6,7,17,18,\ldots,22,23,513,514,\ldots,1000\}$$ with $$ 3+7+488 = 498 $$ elements.

---

This is not the only possible $T$ with $498$ elements, though. For example, $$ \{5,6,7,17,18,\ldots,22,23,24,513,514,\ldots,999\}$$ would also work.

Answer 2

According to the approach described by Henning Makholm if $S=\{1,2,\dots,n\}$ it seems that the maximum size of such set $T(n)$ is related to $[n]_2$ (the binary expansion of $n$). It should be $$|T(n)|=\frac{n-\mbox{number of runs in $[n]_2$}}{2}$$ For $n=1000$ then $[n]_2=1111101000$ and $$|T(1000)|=\frac{1000-4}{2}=498.$$ Is there any connection between Gray code and this problem?

Answer 3

This is not a solution, but some random thought you might find usefull.

If $a + a = 2a$ is a power of two, then a must be a power of two.

For every $a \neq 1$ that is a power of two we can't include both $a+b$ and $a-b$, where $b$ is odd and $a > b$. Thus, a choice is to be made, and it feels like one should include $a-b$ and not $a+b$ since distance between powers of 2 grows but this needs to be proved.

Lastly, any even number a that is not a power of two is fine to include always.