An upper bound 0.4893562 for the upper density of the integers p+2^k
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
Let A be the set of odd integers of the form p + 2^k with p prime and k >= 0. We prove that the upper density of A is less than 0.489356157186869, improving the bound 0.489440909905826 announced by Patankar in November 2026. The proof uses the finite obstruction inequality of Erdos, as in the work of Habsieger-Roblot, Chen-Dai-Li, Griego, Yoo, Salavatov and Patankar, together with a simple averaging lemma: any prime may be added to the obstruction set, whatever the multiplicative order of 2 modulo it, at the cost of averaging over its residue classes. Adding all odd primes below 200 000 to Patankar's 59-prime certificate gives the bound. Starting instead from Salavatov's 51-prime certificate, whose base histogram we rebuilt, gives the bound 0.489419333025262, which also improves the previous record. The certificates are exact rational computations and are provided with the verification programs.
Provenance statement
Tools used
- Anthropic
- Claude Opus
References
- Y. Chen, X. Dai, H. Li, Some computational results on a conjecture of de Polignac about numbers of the form , J. Number Theory (2025), doi:10.1016/j.jnt.2024.07.004; arXiv:2402.06644.arXivDOI
- P. Erdős, On integers of the form and some related problems , Summa Brasil. Math. 2 (1950), 113--123.
- S. Griego, C45 Romanoff upper-density certificate , GitHub (2026), https://github.com/sebastian-griego/c45-romanoff-certificate.link
- L. Habsieger, X.-F. Roblot, On integers of the form , Acta Arith. 122 (2006), 45--50.
- V. Patankar, A 34-prime-base obstruction certificate for Romanoff's constant: , GitHub (2026), https://github.com/vidigoat/optimization-records, directory tao/certificates/c45/v3 .link
- R. Salavatov, Romanoff's constant: , GitHub (2026), https://github.com/fortunto2/romanoff-c45.link
- T. Tao et al., Optimization constants in mathematics , constant 45a, https://teorth.github.io/optimizationproblems/constants/45a.html.link
- A. Yoo, An improved upper bound on Romanoff's constant , GitHub (2026), https://github.com/andrew-yoo/romanoff, tag v3.link
Version history
- v1 · 4 pagesSubmitted by David Niedbala GiraudinInitial depositCurrentNov 17, 2026