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.

Writing $A$ for this set, an explicit finite obstruction computation gives the upper-density bound \(\overline d(A)<0.490249407811155.\) [G2026-ub-0-490249407811155] If the density exists, this gives the corresponding upper bound for $C_{45}$.

Known upper bounds

Known lower bounds

Certificate for the $0.490249407811155$ upper-density bound

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$.

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).”

Contribution notes

Prepared with assistance from Gemini. This update was prepared with assistance from GPT-5.5 Pro; the construction, arithmetic, and verification script were reviewed by the human contributor.