An upper bound 0.4893562 for the upper density of the integers p+2^k

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theory

Contributed by David Niedbala Giraudin ↗

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

The mathematics, the computations and the writing were produced with Claude (Anthropic) under the author's direction. The result is computer-assisted: it rests on exact rational computations whose programs and data are in the ancillary files and can be rerun. Theorem 1 uses the base histogram published by Patankar; Theorem 2 uses the base histogram of Salavatov, rebuilt for this work.

Tools used

Anthropic
Claude Opus

References

  1. Y. Chen, X. Dai, H. Li, Some computational results on a conjecture of de Polignac about numbers of the form p+2kp+2^k , J. Number Theory (2025), doi:10.1016/j.jnt.2024.07.004; arXiv:2402.06644.arXivDOI
  2. P. Erdős, On integers of the form 2k+p2^k+p and some related problems , Summa Brasil. Math. 2 (1950), 113--123.
  3. S. Griego, C45 Romanoff upper-density certificate , GitHub (2026), https://github.com/sebastian-griego/c45-romanoff-certificate.link
  4. L. Habsieger, X.-F. Roblot, On integers of the form p+2kp+2^k , Acta Arith. 122 (2006), 45--50.
  5. V. Patankar, A 34-prime-base obstruction certificate for Romanoff's constant: C45<0.489440909905826C_{45}<0.489440909905826 , GitHub (2026), https://github.com/vidigoat/optimization-records, directory tao/certificates/c45/v3 .link
  6. R. Salavatov, Romanoff's constant: C45<0.489481743486002C_{45}<0.489481743486002 , GitHub (2026), https://github.com/fortunto2/romanoff-c45.link
  7. T. Tao et al., Optimization constants in mathematics , constant 45a, https://teorth.github.io/optimizationproblems/constants/45a.html.link
  8. A. Yoo, An improved upper bound on Romanoff's constant , GitHub (2026), https://github.com/andrew-yoo/romanoff, tag v3.link

Version history

  1. v1 · 4 pagesSubmitted by David Niedbala GiraudinInitial depositCurrentNov 17, 2026