The set of natural numbers that can be written as a sum of a prime and at most $k$ powers of $2$.
Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of 2?
Erdős described this as 'probably unattackable'. In [ErGr80] Erdős and Graham suggest that no such $k$ exists. Gallagher [Ga75] has shown that for any $\epsilon>0$ there exists $k(\epsilon)$ such that the set of integers which are the sum of a prime and at most $k(\epsilon)$ many powers of 2 has lower density at least $1-\epsilon$. Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of 2 suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers. (The restriction to odd integers is important here - for example, Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ (see [9]) suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$). See also [9], [11], and [16].
Gallagher [Ga75] has shown that for any $ϵ > 0$ there exists $k(ϵ)$ such that the set of integers which are the sum of a prime and at most $k(ϵ)$ many powers of $2$ has lower density at least $1 - ϵ$.
Ref: Gallagher, P. X., Primes and powers of 2.
Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of $2$ suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers.
Ref: Granville, A. and Soundararajan, K., A Binary Additive Problem of Erdős and the Order of $2$ mod $p^2$
Bogdan Grechuk has observed that 1117175146 is not the sum of a prime
and at most $3$ powers of $2$.
There are infinitely many even integers not the sum of a prime and $2$ powers of $2$
Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).