The density of numbers of the form $p + 2^k$ In 1934, Romanoff proved that the following set has positive lower density:
$$\displaystyle \mathcal{R}(x)= \{n \in \mathbb{N} : n \leq x, n = p + 2^k \}$$
where $p$ is a prime and $k \geq 0$ is a non-negative integer. In 2010 Lee proved the analogous result when powers of 2 are replaced by terms in the Fibonacci sequence. Very recently, Ballot and Luca generalized the above to arbitrary non-degenerate linear recurrences (Ballot, Christian, Luca, Florian, On the sumset of the primes and a linear recurrence, Acta Arithmetica 161.1 (2013)).
The basic idea behind the proof is to define $r(n)$ to be the number of ways to write $n$ as the sum of a prime and a term in the linear recurrence considered, and simultaneously obtain a lower bound for $\displaystyle \sum_{n \leq x} r(n) \gg x$ and and upper bound for $\displaystyle \sum_{n \leq x} r(n)^2 \ll x$, and then apply the Cauchy-Schwarz inequality to obtain the desired result.
Thus, the nature of the proof does not yield an explicit constant. So there are two questions that remain unanswered:

*

*Can one obtain an asymptotic for $\#\mathcal{R}(x)$? Is the natural density expected to exist at all?


*Can one obtain an explicit constant for the lower bound $\#\mathcal{R}(x) \gg x$?
Thanks for any insights. It would already be insightful to obtain an answer to the above two inquiries for the case of Romanoff's theorem.
 A: The density is expected to exist, but this seems difficult.
As for question 2, the first explicit lower bound for $\liminf \frac{1}{x}\#\mathcal{R}(x)$ was established by Chen and Sun. I think the most up to date results are due (independently) to Pintz and to Habsieger and Roblot. The relevant references are
Pintz, J. A note on Romanov's constant. Acta Math. Hungar.  112  (2006),  no. 1-2, 1–14.
and
Habsieger, Laurent; Roblot, Xavier-François. On integers of the form $p+2^k$. Acta Arith.  122  (2006),  no. 1, 45–50. 
A: Romani (Calcolo 20 (1983), 319 - 336) gave a heuristic argument leading to the conjecture that the asymptotic density should exist and should be about 0.434... .
The basic idea of the heuristics is that the probability for the event $n=p+2^a$ there are some obvious congruence conditions, but that apart from these conditions these events behave like independent random variables. In this way one can not only obtain a guess for the density, but also a conjectural distribution for the number of integers for which the equation $n=p+2^a$ has exactly $k$ solutions.
