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:


1. Can one obtain an asymptotic for $\#\mathcal{R}(x)$? Is the natural density expected to exist at all?
2. 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.



The density of numbers of the form $p + 2^k$
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](http://link.springer.com/article/10.1007%2Fs10474-006-0060-6). 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$](http://journals.impan.pl/cgi-bin/doi?aa122-1-4). Acta Arith. 122 (2006), no. 1, 45–50. 


