On computing the density of integers of the form 2ⁿ+𝑝

Del Corso, Gianna; Del Corso, Ilaria; Dvornicich, Roberto; Romani, Francesco

doi:10.1090/mcom/3537

On computing the density of integers of the form $2^n+p$
HTML articles powered by AMS MathViewer

by Gianna M. Del Corso, Ilaria Del Corso, Roberto Dvornicich and Francesco Romani HTML | PDF

Math. Comp. 89 (2020), 2365-2386 Request permission

Abstract:

The problem of finding the density of odd integers which can be expressed as the sum of a prime and a power of two is a classical one. In this paper we tackle the problem both with a direct approach and with a theoretical approach, suggested by Bombieri. These approaches were already introduced by Romani in [Calcolo 20 (1983), no. 3, pp. 319–336], but here the methods are extended and enriched with statistical and numerical methodologies. Moreover, we give a proof, under standard heuristic hypotheses, of the formulas claimed by Bombieri, on which the theoretical approach is based. The different techniques produce estimates of the densities which coincide up to the first three digits.

References

Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, DOI 10.1090/S0025-5718-1962-0148632-7
P. T. Bateman and R. A. Horn, Primes represented by irreducible polynomials in one variable. Proc. Symp, in Pure Math. 8 (1965), 119–132.
E. Bombieri, Private communication, 1977.
Tony F. Chan, Gene H. Golub, and Randall J. LeVeque, Algorithms for computing the sample variance: analysis and recommendations, Amer. Statist. 37 (1983), no. 3, 242–247. MR 713834, DOI 10.2307/2683386
Yong-Gao Chen and Xue-Gong Sun, On Romanoff’s constant, J. Number Theory 106 (2004), no. 2, 275–284. MR 2059075, DOI 10.1016/j.jnt.2003.11.009
A. de Polignac, Réchèrches nouvelles sur les nombres premieres, C. R. Acad. Sci. Paris Sér. 29 (1849), "397–401".
P. Erdös, On integers of the form $2^k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113–123. MR 44558
Laurent Habsieger and Xavier-François Roblot, On integers of the form $p+2^k$, Acta Arith. 122 (2006), no. 1, 45–50. MR 2217322, DOI 10.4064/aa122-1-4
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
W. Kahan, Further remarks on reducing truncation errors, Commun. ACM 8 (1965), no. 1, 40.
Hongze Li and Hao Pan, The Romanoff theorem revisited, Acta Arith. 135 (2008), no. 2, 137–142. MR 2453528, DOI 10.4064/aa135-2-3
M. Madritsch and S. Planitzer, Romanov’s theorem in number fields, Tech. report, arXiv:arXiv:1512.04869, 2015.
Hao Pan and Wei Zhang, On the integers of the form $p^2+b^2+2^n$ and $b^2_1+b^2_2+2^{n^2}$, Math. Comp. 80 (2011), no. 275, 1849–1864. MR 2785483, DOI 10.1090/S0025-5718-2011-02445-2
J. Pintz, A note on Romanov’s constant, Acta Math. Hungar. 112 (2006), no. 1-2, 1–14. MR 2251126, DOI 10.1007/s10474-006-0060-6
F. Romani, Computations concerning primes and powers of two, Calcolo 20 (1983), no. 3, 319–336 (1984). MR 761788, DOI 10.1007/BF02576468
F. Romani, Computer techniques applied to the study of additive sequences, Ph.D. thesis, Scuola Normale Superiore di Pisa, 1978. Supervisor: E. Bombieri.
N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), no. 1, 668–678 (German). MR 1512916, DOI 10.1007/BF01449161
A. Schinzel, Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers”, Acta Arith. 7 (1961/62), 1–8. MR 130203, DOI 10.4064/aa-7-1-1-8
A. Schinzel, A remark on a paper of Bateman and Horn, Math. Comp. 17 (1963), 445–447. MR 153647, DOI 10.1090/S0025-5718-1963-0153647-X
J. G. van der Corput, On de Polignac’s conjecture, Simon Stevin 27 (1950), 99–105 (Dutch). MR 35298
R. C. Vaughan, The Hardy-Littlewood method, Cambridge Tracts in Mathematics, vol. 80, Cambridge University Press, Cambridge-New York, 1981. MR 628618