---

Claim. There is a set $A\subset\mathbb{N}$ with

$$\lvert A\cap\{1,\ldots,N\}\rvert\sim\frac{N}{\log_2 N}$$

as $N\to\infty$ such that every sufficiently large integer is $2^k+a$ with $k\ge 0$ and $a\in A$. Such an $A$ is an exact additive complement of the powers of two: since the integers up to $N$ use at most $\log_2 N+1$ powers of two, every complement has at least $(1+o(1))N/\log_2 N$ elements up to $N$, so the count is best possible. This sharpens the construction of Ruzsa 1972, which gives $\ll N/\log N$ with an unspecified constant, and it settles Problem 221 with the optimal constant. The library holds no copy of the paper; the statement follows the site's remark.

Depends on. No page of this wiki; the result is the paper's.

Acceptance. Refereed: I. Z. Ruzsa, Additive completion of lacunary sequences, Combinatorica 21 (2001), no. 2, 279–291, published 2001-04-01. Reviewed: the site's curator, T. F. Bloom, records this result at erdosproblems.com as giving the sharpest possible count for the problem, which is the site's acceptance. No Lean formalization of the asymptotic statement is recorded; the formalization linked from the 1972 page covers the $\ll N/\log N$ bound.