ON INTEGERS OF THE FORM p + 2k

Laurent Habsieger and Xavier-François Roblot
Abstract. We investigate the density of integers that may be written as
p + 2k , where p is a prime and k a nonnegative integer.

1. Introduction
Troughout this paper, the symbol p will denote a prime and k will bea nonnegative integer. Romanov [5] proved that the integers of the form
p + 2k have positive density. He also raised the following question : does
there exists an arithmetic progression consisting only of odd numbers, noterm of which is of the form p + 2k ? Erdős [1] found such an arithmetic
progression by considering integers which are congruent to 172677 modulo
5592405 = (224 − 1)/3. Thus the density of numbers of the form p + 2k
is less than 1/2, the trivial bound obtained from the odd integers. For
convenience we introduce#{p + 2k ≤ x}x→∞
x/2

d = lim inf

andd = lim supx→∞#{p + 2k ≤ x}.
x/2

The aim of this paper is to give an explicit version of the estimates 0 <d ≤ d < 1.
Theorem 1. We have0.1866 < d ≤ d < 0.9819 .
This range is pretty large and Bombieri conjectured the more precise
value 0.868 (see [4]).
In section 2, we obtain the lower bound 0.1866 < d, by slightly refining
a straightforward application of a recent result of Pintz and Ruzsa [3],in their study of Linnik’s approximation of Goldbach problem (see also[2,3]). In section 3, we get the upper bound, using computations on residue
classes.
1991 Mathematics Subject Classification. Primary 11P32 ; Secondary 11Y35, 11Y60.
Partially supported by the European Community IHRP Program, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-200100272.
Typeset by AMS-TEX

1

2LAURENT HABSIEGER AND XAVIER-FRANÇOIS ROBLOT

2. The lower bound
Let N be a large integer and put L = ⌊log N/ log 2⌋. Define the functionsr(n) = #{(p, k) : n = p + 2k , p ≤ N , 1 ≤ k ≤ L}
ands(N ) = #{(p1 , p2 , k1 , k2 ) : p1 −p2 = 2k2 −2k1 , pj ≤ N, 1 ≤ kj ≤ L, j = 1, 2}
so thats(N ) =NX

r 2 (n) .

n=1

Pintz and Ruzsa [3] proved the following lemma.
Lemma 1. For N large enough, we haves(N ) ≤2CN ,log2 2

where C < 5.3636.
Let d(N ) denote the number of positive integers n ≤ N which may be
written in the form n = p + 2k . The Cauchy-Schwarz inequality implies
easily that(π(N )L)2 ≤ d(N )s(N ) ,where π(N ) denotes the number of primes p ≤ N . We deduce from Lemma
1 and from the prime number theorem that 2Cd(N ) ≥ (1 + o(1))N , andthe lower bound d ≥ 1/C > 0.1864 follows from the definitions.
To get the bound from the theorem, we need further notations. PutǫN =P1≤n≤N , r(n)>0 r(n)P1≤n≤N , r(n)>0 1andǫ=2.
d log 2

By the definitions, there exists a subsequence of (ǫN )N∈N which convergesto ǫ. Let us now refine the Cauchy-Schwarz inequality by studying
X∆N =(r(n) − ǫN )2 ,1≤n≤N , r(n)>0so thatP

1≤n≤N r(n)2(π(N )L)2= s(N ) −∆N =d(N )1≤n≤N , r(n)>0 1
1≤n≤N
12N≤ 5.3636 − + o(1),dlog2 2X

2r (n) − P

ON INTEGERS OF THE FORM p + 2k

3for infinitely many N . Without loss of generality we may assume thatǫ ∈]15, 15.5[: otherwise we would get either d ≥ 0.19 which would bebetter, or d ≤ 0.1862 which is false. For infinitely many N we thus haveXX
∆N ≥(15 − ǫN )2 ≥ (15 − ǫ)2 + o(1) N1≤n≤N , r(n)>01≤n≤N , r(n)>0d2=15 −2d log 22!

+ o(1) N .

We deduce from these estimates the inequality
d2


15 −

2d log 222≤
log2 2
15.3636 −,dwhich may be written as
56.25 log2 2d2 − (15 log 2 + 5.3636)d + 1 ≤ 0 .
The lower bound d ≥ 0.1866 then follows.
3. The upper bound
A. Basic ideas.
Let us introduce further notations. Let M be a positive odd integer
and let ω denote the order of 2 in (Z/M Z)∗ . For m a residue class modulo
M , putfM (m) = {k ∈ Z/ωZ : m − 2k ∈ (Z/M Z)∗ } ,andδM (ν) = |{m ∈ Z/M Z : |fM (m)| = ν}| .
The basic tool to get an upper bound for d is the following lemma.
Lemma 2. With the previous notations, we haved≤ωX

δM (ν) min

ν=0

2ν
1,
M ωϕ(M ) log 2,where ϕ denotes Euler’s function.
Proof. Let m be a congruence class modulo M , with |fM (m)| = ν. Let us
study the proportion of odd integers congruent to m that may be written
in the form p + 2k . This proportion is clearly at most 1/M , and we only
need to prove the alternative upper bound.
Since all the primes but a finite number are invertible modulo M , thereexist ν congruence equations m = pi + 2ki , i ∈ {1, . . . , ν}, such thatall but finitely many representations p + 2k come from one of these congruence equations. The number of primes up to N which are congruent to pi modulo M is asymptotic to N/(ϕ(M ) log N ), while the numberof powers of 2 which are congruent to 2ki modulo M is asymptotic to4

LAURENT HABSIEGER AND XAVIER-FRANÇOIS ROBLOTlog N/(ω log 2). Thus the number of integers congruent to m that may be
written in the form p + 2k is at most (ν/(ϕ(M )ω log 2) + o(1))N . Thisimplies that the proportion of odd integers enjoying these properties is at
most 2ν/(ϕ(M )ω log 2) and the lemma follows.
This lemma provides a non trivial upper bound for d as soon as there
exist residue classes m modulo M such thatfM (m) <ωϕ(M ) log 2,
2M(1)

a condition that occur for a small number of classes. The main problem isto compute the distribution of the fM (m)’s in an efficient way. The directcomputation of all the fM (m)’s is quickly limited by memory problems.
However one can obtain significant results this way.
Take M = 23205 = (224 − 1)/723, so that ω = 24 and ϕ(M ) = 9216.
The condition (1) is equivalent to fM (m) ≤ 3. We find(δM (0), δM (1), δM (2), δM (3)) = (0, 48, 720, 320) ,and we get this way d ≤ 0.985049.
B. Refined algorithms and results.
It appears that the function fM takes very few possible values, whencompared to the subset set of Z/ωZ. So let us introduce
gM (I) = {m ∈ Z/M Z : fM (m) = I} and GM (I) = |gM (I)| ,for I ⊂ Z/ωZ. Note that
δM (ν) =X

GM (I) .

|I|=ν

So it is sufficient to know the distribution of the GM (I)’s to compute anupper bound for d.
The main advantage of the function gM is that it is easily computableby induction on the number of prime factors of M . The initial case isgiven by g0 ({0}) = {0}.
Let M1 , M2 be two positive odd squarefree integers, with M2 = pM1for some prime p not dividing M1 . Let ω1 , ω2 and ωp denote the order of
2 in (Z/M1 Z)∗ , (Z/M2 Z)∗ and (Z/pZ)∗ , respectively. The image of fp iseasy to compute. There is the subset Ip,0 = {2̄k̄ ∈ (Z/pZ)∗ : k̄ ∈ Z/ωp Z}
with Gp (Ip,0 ) = p − ωp , for each j̄ ∈ Z/ωp Z the subset Ip,j̄ = {2̄k̄ ∈(Z/pZ)∗ : k̄ ∈ Z/ωp Z, k̄ 6= j̄} with Gp (Ip,j̄ ) = 1. Now, let I2 and Ip bein the image of fM2 and fp respectively. Denote by I˜2 and I˜p the subsetsof Z/M1 Z which are inverse images of I2 and Ip by the map on subsets
induced by the natural surjections Z/M1 Z → Z/M2 Z and Z/M1 Z → Z/pZ
respectively. Then it is easy to see that I˜2 ∩ I˜p is in the image of fM1 with
GM1 (I˜2 ∩ I˜p ) = GM2 (I2 )Gp (Ip ), and that all subsets in the image of fM1
are obtained in this way.

ON INTEGERS OF THE FORM p + 2k5This construction allows to build recursively the image of fM . It alsoenables us to know how many classes have the same image. Therefore, one
can compute GM (I) without knowing gM (I).
Let us give an example. For M = 5592405 = 3.5.7.13.17.241 = (224 −1)/3, we have ω = 24. There are 16401 subsets in the image of fM , which
is much fewer than 224 . Each of these subsets is obtained in r ways, with1 ≤ r ≤ 250068. Only subsets of cardinality at most 3 lead to an improved
upper bound. The empty set appears 48 times. Each of the singletons fromZ/24Z appears 540 times. For 2-subsets, the situation is slightly more
complicated to describe. The subsets of the form {a, a ± 8} appear 3625
times (there are 24 of them) while those of the form {a, a + 12} appear
7170 times (there are 12 of them). There are 224 interesting 3-subsets,appearing 3, 6, 225 or 9520 times.
This method requires much less memory than the algorithm from theprevious subsection. It is still possible to save a bit more memory. Indeed
the representation problem (by an invertible plus a power of 2) is invariantwhen multiplied by a power of 2. So we can use a representative of acollection of subsets, each of them being obtained by translation from therepresentative, instead of subsets of Z/ωZ.
The best result found so far is given by
M = 3.5.7.11.13.17.19.31.41.73.241.257 .
It leads to the improvementd < 0.9818818607968211912960156368 ,and the upper bound from Theorem 1 follows. This computation took 35
minutes on an Intel Xeon 2.4GHz with a memory stack of 2.1Go. Indeed,
the real limitation is the memory. Note that during the computations,subsets for which GM (I) was quite large and thus unlikely to contributein the density were dropped (still there were a total of 4469837 different
subsets at the end). Hence the density obtained may be a little bigger
than the actual density for this value of M .
Addendum
The referee informed the authors that, during the refereeing process,
Janos Pintz would have improved on the lower bound. In a paper toappear in Acta Math. Hung., he would show d ≥ 0.18734 by a moreelaborate method.
References
1. P. Erdős, On integers of the form 2k + p and some related problems, Summa Brasil.
Math. 2 (1950), 113–123.
2. D. R. Heath-Brown and J.-C. Puchta, Integers represented as a sum of primes andpowers of two, Asian J. Math. 6 (2002), 535–565.
3. J. Pintz and I. Z. Ruzsa, On Linnik’s approximation to Goldbach’s problem, I, Acta
Arith. 109.2 (2003), 169–194.
4. F. Romani, Computations concerning primes and powers of two, Calcolo 20 (1983),
319–336.

6LAURENT HABSIEGER AND XAVIER-FRANÇOIS ROBLOT

5. N. P. Romanov, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109(1934), 668–678.
CNRS UMR 5208 Mathématiques, Université Claude Bernard Lyon 1, 43
boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, FRANCE
E-mail address: Laurent.Habsieger@math.univ-lyon1.fr,roblot@math.univ-lyon1.fr