Density of odd integers that are the sum of a prime and a power of two ($C_{45}$)

The current record is Yoo's $0.490180063290061$ ([Y2026]); that bound has no printed certificate on this page. The object below recomputes Griego's earlier value.

Let

$$A=\{n\text{ odd}: n=p+2^k\text{ for some prime }p\text{ and }k\ge0\}.$$

The certificate uses the finite prime set

$$\begin{aligned} \mathcal P=\{& 3,5,7,11,13,17,19,23,29,31,37,41,47,61,73,89,167,223,\\ &233,263,359,383,431,439,479,1103,1433,1913,2089,2351,4513,\\ &5737,8191,9719,176383,178481 \}. \end{aligned}$$

Put $M=\prod_{q\in\mathcal P}q$ and $T=\operatorname{lcm}_{q\in\mathcal P}\operatorname{ord}_q(2)$. For each residue class $a\pmod M$, let

$$F(a)=\{r\pmod T:\gcd(a-2^r,M)=1\},\qquad \nu(a)=|F(a)|,$$

and let $\delta(\nu)=\#\{a\pmod M:\nu(a)=\nu\}$.

The obstruction argument gives

$$\overline d(A) \le \sum_\nu \delta(\nu) \min\left( \frac1{2M}, \frac{\nu}{T\varphi(M)\log 2} \right).$$

The external verifier independently recomputes the 13-prime seed histogram from the residue conditions, applies the exact coprime-order cluster updates, and then evaluates the final rational upper bound using a rigorous lower bound for $\log 2$.

• In the (unlikely) event that this set fails to have a density, the upper and lower bounds should be interpreted as bounds on the upper and lower densities, respectively.
• Variants of this set are studied in Erdős problems #205, #244 and #851.

References (from the repository page)

• [CDL2024] Y. Chen, X. Dai, and H. Li, "Some results on a conjecture of de Polignac about numbers of the form $p + 2^k$," arXiv:2402.06644, 2024.

• [CS2004] Y.G. Chen and X.G. Sun, "On Romanoff's constant," J. Number Theory, 106 (2004), 275–284.

• [CE2018] C. Elsholtz and J.-C. Schlage-Puchta, "On the density of sums of primes and powers of two," Acta Arithmetica, 183 (2018), 1-20.

• [E1950] P. Erdős, "On integers of the form $2^k+p$ and some related problems," Summa Brasil. Math., 2 (1950), 113–123.

• [HR2006] L. Habsieger and X. Roblot, "On integers of the form $p + 2^k$," Acta Arithmetica, 122 (2006), 45–50.

• [HS2010] L. Habsieger and R. Sivak-Fischler, "A new lower bound for Romanoff's constant," Journal of Number Theory, 130 (2010).

• [P2006] J. Pintz, "A note on Romanoff's constant," Acta Mathematica Hungarica, 112 (2006), 1-14.

• [R1934] N. P. Romanoff, "Über einige Sätze der additiven Zahlentheorie," Math. Ann., 109 (1934), 668–678.

• [G2026] Griego, Sebastian. 36-prime obstruction certificate for Romanoff's constant upper-density bound, 2026. Code and verification.

• [G2026-ub-0-490249407811155] loc: external verifier repository, verify_all.sh. quote: "The exact rational verifier proves the upper-density bound (\overline d(A)<0.490249407811155)."

• [Y2026] Yoo, Andrew, "An improved upper bound on Romanoff's constant," 2026. https://github.com/andrew-yoo/romanoff/tree/v3.

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.107648; best known upper bound 0.490180063290061. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound	Reference	Comments
$1/2=0.5$	Trivial
$<0.5$	[E1950]	Used covering systems
$0.490941$	[HR2006]
$0.490341088858244$	[CDL2024]
$0.490249407811155$	[G2026]	36-prime finite obstruction certificate with exact cluster-update verification.
$0.490180063290061$	[Y2026]

Known lower bounds

Bound	Reference	Comments
$0$	Trivial
$>0$	[R1934]
$0.0868$	[CS2004]
$0.0936$	[P2006]
$0.093627$	[HS2010]
$0.107648$	[CE2018]