Romanoff's constant

Description of constant

$C_{45}$ is the asymptotic density (if it exists) of the set of odd integers that can be expressed as the sum of a prime number and a power of two.

Known upper bounds

Known lower bounds

Certificate for the superseded $0.490249407811155$ Griego bound

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\ge 0\}.$$ The certificate uses the finite prime set $$\begin{array}{rl}\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{array}$$ Put $M={\prod }_{q\in \mathcal{P}}q$ and $T={\mathrm{lcm}}_{q\in \mathcal{P}}{\mathrm{ord}}_q(2)$. For each residue class $a(\mathrm{mod}M)$, let $$F(a)=\{r(\mathrm{mod}T):\gcd (a-2^r,M)=1\},\nu (a)=|F(a)|,$$ and let $\delta (\nu )=\#\{a(\mathrm{mod}M):\nu (a)=\nu \}$.

The obstruction argument gives $$\overline{d}(A)\le \sum _{\nu }\delta (\nu )\min \left(\frac{1}{2M},\frac{\nu }{T\phi (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$.

Additional comments and links

• 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

• [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.

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.