---

Claim. There is a set $A\subset\mathbb{N}$ with $\lvert A\cap\{1,\ldots,N\}\rvert\ll N/\log N$ for all large $N$ such that every sufficiently large integer is $2^k+a$ with $k\ge 0$ and $a\in A$. The two-page note Ruzsa 1972 takes for $A$ the integers of the form $5^u v$ and $5^u v+1$ with $5^u>c\log v$ for a small absolute constant $c>0$. Representability rests on $2$ being a primitive root modulo every power of $5$: for large $n$ choose $r$ with $5^r\approx\log n$; some $k<5^r$ makes $n-2^k$ or $n-2^k-1$ divisible by $5^r$, and the quotient $v$ satisfies $5^r>c\log v$. The note also observes that every $n$ has a bounded number of such representations, and that the constant in the counting bound must be at least $\log 2$, since the integers up to $N$ use at most $\log_2 N+1$ powers of two. Lorentz [Lo54] had earlier given a set with the weaker bound $\ll N\log\log N/\log N$. The site's thread records that $c=1/(5\log 2)$ works, with $A=\{5^n m: 1\le m<2^{5^{n+1}}\}+\{0,1\}$ and every $N\ge 32$ represented with $k\ge 1$.

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

Acceptance. Refereed: I. Z. Ruzsa, On a problem of P. Erdős, Canad. Math. Bull. 15 (1972), no. 2, 309–310; the issue is dated June 1972, and the page name uses the first day of that month. Reviewed: the site's curator, T. F. Bloom, labels Problem 221 proved at erdosproblems.com on this result, which is the site's acceptance. An outside Lean file, produced by Harmonic's Aristotle from an explicit rewriting of Ruzsa's proof, as its header says, announced on the site's thread on 2026-01-31 and pinned at its commit of 2026-03-13, proves thm_main: a set whose counting function is at most $cx/\log x$ for all large $x$ and which represents every large $N$ as $2^k+a$ with $k\ge 1$; the announcement notes that the note asserts the counting bound without proof and that the formalization supplies it. formal-conjectures links this file for its erdos_221 statement, tagged research solved (221.lean as of 2026-10-07). The file is not part of this repository's audited Lean, so formalized is not listed and the Lean qualification of the site's label is the site's.