Counting Primes whose Sum of Digits is Prime

Glyn Harman Department of Mathematics Royal Holloway, University of London Egham Surrey TW20 0EX United Kingdom

                      g.harman@rhul.ac.uk

Abstract

Motivated by recent work of Drmota, Mauduit and Rivat, we discuss the possibility of counting the number of primes up to x whose sum of digits is also prime. We show that, although this is not possible unless we assume a hypothesis on the distribution of primes stronger than what is implied by the Riemann hypothesis, we can establish a Mertens-type result. That is, we obtain a formula for the number of such primes p up to x weighted with a factor 1/p. Indeed, we can iterate the method and count primes with the sum of digits a prime whose sum of digits is a prime, and so on.

1 Introduction

Thanks to the revolutionary work of Mauduit and Rivat [7], in particular as developed in [2], our knowledge of the distribution of primes with constraints on their sum of digits has undergone a substantial expansion in recent years. The question of counting the number of primes up to x, whose sum of digits in base b is also prime, would have been considered far too difficult ten years ago in view of the difficulty in restricting the sum of digits function when its variable is prime. In this paper we discuss this question, showing that it is still impossibly difficult at present, but this is now a result of our lack of knowledge concerning the distribution of primes in short intervals, and no longer caused by the problems of restricting the sum of digits function. However, we are able to prove a Mertens-type result on counting primes whose sum of digits is prime. Throughout this paper the letters p and q are reserved for prime variables. In 1874 Mertens proved that

∑_{p<X} \frac{1}{p} = log log X + A + O((log x)^{−1}),

for a certain constant A (see [1, p. 56]). In this paper we will obtain analogues of this result for primes whose sum of digits written in base b (b ≥ 2) are also prime. For brevity we shall write this set as P_{b}. If

n = ∑_{k=0}^{r} a_{k}b^{k}, 0 ≤ a_{k} ≤ b − 1, then we put σ_{b}(n) = ∑_{k=0}^{r} a_{k}

for the sum of digits function in base b. In fact we shall be able to iterate our working and establish Mertens-type theorems for primes belonging to sets defined as follows:

P_{b}^{(1)} = P_{b}, P_{b}^{(j)} = {p ∈ P_{b} : σ_{b}(p) ∈ P_{b}^{(j−1)}}, j = 2, 3 ….

We write log_{b} x for the logarithm to base b, log x for the natural logarithm, and define L_{j}(x) inductively by

L_{1}(x) = max(1, log x), L_{j}(x) = L_{1}(L_{j−1}(x)) for j ≥ 2.

Our starting point will be a remarkable theorem of Drmota, Mauduit and Rivat [2]. Before stating the result precisely we need the following notation:

s_{b} = \frac{b^{2} − 1}{12}, μ_{b} = \frac{1}{2}(b − 1), S(k, x) = |\{p ≤ x : σ_{b}(p) = k\}| .

As usual we write ϕ(n) for Euler’s totient function, and π(x) for the number of primes up to x. We recall the prime number theorem in the form

π(x) = \frac{x}{log x} + O (\frac{x}{(log x)^{2}} ) .  (1)

Theorem 1 (Drmota/Mauduit/Rivat). We have, uniformly for all integers k ≥ 0 with (k, b − 1) = 1,

S(k, x) = \frac{b − 1}{ϕ(b − 1)} \frac{π(x)}{\sqrt{2πs_{b} log_{b} x}} (exp (−\frac{(k − μ_{b} log_{b} x)^{2}}{2s_{b} log_{b} x} ) + O ((log x)^{− \frac{1}{2} +ϵ})) , (2)

where ϵ > 0 is arbitrary but fixed.

Since σ_{b}(p) ≡ p (mod b − 1), for all but the finitely many primes p satisfying (p, b − 1) > 1 we have (σ_{b}(p), b − 1) = 1, and this leads to the (b − 1)/ϕ(b − 1) factor appearing frequently. From the above result we can deduce some very interesting corollaries. Clearly, (2) shows that every sufficiently large integer is the sum of digits of a prime number. So, in particular, there are infinitely many primes whose sum of digits is also prime. Also, every sufficiently large prime is the sum of digits of another prime which in turn is the sum of digits of another prime, and so on. We use Theorem 1 to obtain a Mertens-type result as follows.

Theorem 2. Let b ≥ 2 be an integer and X ≥ 2. Then we have

∑_{\begin{matrix}p<X \\ p∈P_{b} \end{matrix}} \frac{1}{p} = \frac{b − 1}{ϕ(b − 1)}L_{3}(X) + O(1).  (3)

In fact we shall use Theorem 2 as the first step in an inductive argument to establish the following more general result for the sets P_{b}^{(j)}.

Theorem 3. Let b, j ≥ 2 be integers and X ≥ 2. Then we have

∑_{\begin{matrix}p<X \\ p∈P_{b}^{(j)} \end{matrix}} \frac{1}{p} = (\frac{b − 1}{ϕ(b − 1)})^{j} L_{j+2}(X) + O(1).  (4)

As a final application of Theorem 1 we leave the following for the reader to prove.

Theorem 4. Write P_{b}^{∗} for the set of primes in P_{b} which have a prime number of digits. Then

∑_{\begin{matrix}p<X \\ p∈P_{b}^{∗} \end{matrix}} \frac{L_{2}(p)}{p} = \frac{b − 1}{ϕ(b − 1)}L_{3}(X) + O(1).

2 The problem of the unweighted sum

In this section we briefly consider the sum

π_{b}^{∗}(X) = ∑_{\begin{matrix}p<X \\ p∈P_{b} \end{matrix}} 1 .

First we note the following result of Kátai [5].

Lemma 5. For every positive integer k we have

∑_{p<x} |σ_{b}(p) − μ_{b} log_{b} x|^{k} ≪_{k} x(log x)^{k/2−1}.

Now, even assuming the Riemann hypothesis and the pair correlation conjecture [3] we cannot prove that every interval I_{y} = [y−y^{\frac{1}{2}} (log y)^{\frac{1}{3}} , y+y^{\frac{1}{2}} (log y)^{\frac{1}{3}} ] contains a prime number. Suppose that I_{y} contains no primes, and choose X so that y = μ_{b} log_{b} X. Then Theorem 1 cannot supply an asymptotic formula for π_{b}^{∗}(X), and by Lemma 5 with k = 3A

π_{b}^{∗}(X) ≪_{A} \frac{X}{XL_{1}(X)(L_{2}(X))^{A}}

for every positive integer A. This shows that no asymptotic formula is possible unless a stronger result than can be obtained on the Riemann hypothesis is assumed, for clearly π_{b}^{∗}(X) should be of size X(L_{1}(X)L_{2}(X))^{−1}. We state here a hypothetical result to illustrate what we mean.

Theorem 6. Suppose that there exists a positive function f(x) → 0 such that for all large x every interval of the form [x, x + x^{\frac{1}{2}} f(x)] contains f(x)x^{\frac{1}{2}} (1 + o(1))(log x)^{−1} primes. Then

π_{b}^{∗}(X) ∼ \frac{b − 1}{ϕ(b − 1)} \frac{X}{L_{1}(X)L_{2}(X)}.  (5)

The proof of this result is straightforward. By Lemma 5 we need only count primes whose sum of digits is q with

|q − μ_{b} log_{b} x| < (log_{b} x)^{\frac{2}{3}} .  (6)

Applying Theorem 1 we need to estimate

∑_{(6)} exp (−\frac{(q − μ_{b} log_{b} x)^{2}}{2s_{b} log_{b} x} ) .

Breaking the summation range into shorter ranges of the form [y, y + y^{\frac{1}{2}} f(y)] and then comparing a sum with an integral we obtain

\frac{1 + o(1)}{log(μ_{b} log_{b} x)} ∫_{−∞}^{∞} exp (−\frac{t^{2}}{2s_{b} log_{b} x}) dt = \frac{1 + o(1)}{log(μ_{b} log_{b} x)}\sqrt{2s_{b}π log_{b} x},

which quickly establishes the result.

We remark that the hypothesis of Theorem 6 is “almost always” true unconditionally in the following sense. The method of Heath-Brown [4] shows that, given ϵ > 0, there exists η > 0 such that for all integers y ∈ [Y, 2Y), with at most ≪ Y ^{\frac{3}{4} +ϵ} exceptions, every subinterval [z, z + z^{\frac{1}{2} −η}] of [y − Y ^{\frac{1}{2} +ϵ}, y + Y ^{\frac{1}{2} +ϵ}] contains z^{\frac{1}{2} −η}(1 + O((log z)^{−1}))(log z)^{−1} primes. For these non-exceptional y and with X chosen to satisfy y = μ log_{b} X we then have (5). Indeed, we can obtain the expected asymptotic formula for X on quite long ranges. We note that we are unable to use the stronger results obtainable using a sieve method [6] since we require an asymptotic formula for the number of primes in an interval rather than upper or lower bounds.

3 Proof of Theorem 2

Lemma 5, together with (2), shows that σ_{b}(p) is concentrated near its mean value μ_{b} log_{b} p, and so enables us to restrict our attention to certain p ∈ P_{b} with negligible error. We write

M(m) = exp ((log b)m^{\frac{7}{8}} ) ,  μ(m) = μ_{b}m^{\frac{7}{8}} ,
ϵ(m) = \frac{M(m + 1) − M(m)}{M(m)},  δ(m) = (m + 1)^{\frac{7}{8}} − m^{\frac{7}{8}} ,

and put M(m) = [M(m), M(m + 1)). We note for future reference that

ϵ(m) = O (m^{− \frac{1}{8}} ) and ϵ(m) = δ(m) (log b + O (m^{− \frac{1}{8}} )) .  (7)

Let V be the largest integer with M(V) < X. Also, write

P(m) = \{p ∈ P_{b} : σ_{b}(p) = q, |q − μ(m)| < q^{\frac{2}{3}} \}.

We remark that the exponents \frac{7}{8}, \frac{2}{3} above are chosen as convenient fixed numbers between \frac{1}{2} and 1 (which must satisfy certain inequalities to enable certain sums to converge later) and have no other special significance. From Lemma 5 we can deduce that

∑_{m=1}^{∞} ∑_{\begin{matrix}p∈M(m) \\ p∈P_{b},p∉P(m) \end{matrix}} \frac{1}{p}

converges. Hence

S(X) := ∑_{\begin{matrix}p<X \\ p∈P_{b} \end{matrix}} \frac{1}{p} = ∑_{m≤V} \frac{1}{M(m)} ∑_{\begin{matrix}p∈M(m) \\ p∈P(m) \end{matrix}} 1 + O(1).

Now write Q = log_{b} X. Then

S(X) = ∑_{q<Q} ∑_{\begin{matrix}m≤V \\ |q−μ(m)|<q^{\frac{2}{3}} \end{matrix}} \frac{1}{M(m)} ∑_{\begin{matrix}p∈M(m) \\ σ_{b}(p)=q \end{matrix}} 1 + O(1).

After applications of Theorem 1 with ϵ = 1/14 and using (1) this becomes

∑_{q<Q} ∑_{\begin{matrix}m≤V \\ |q−μ(m)|<q^{\frac{2}{3}} \end{matrix}} \frac{b − 1}{ϕ(b − 1)} \frac{ϵ(m)}{(log b)m^{\frac{7}{8}} \sqrt{2πs_{b}m^{\frac{7}{8}}}} (exp (−\frac{(q − μ(m))^{2}}{2s_{b}m^{\frac{7}{8}}} ) + O(m^{− \frac{1}{4}} )) . (8)

Now the O(m^{− \frac{1}{4}} ) term in the above leads to an error (using m = (q/μ_{b})^{\frac{8}{7}} + O(q^{\frac{8}{7} − \frac{1}{3}} ))

≪ ∑_{q<Q} q^{\frac{8}{7} − \frac{1}{3}} q^{− \frac{1}{7}} q^{−1}q^{− \frac{1}{2}} q^{− \frac{2}{7}} = O(1),

and so we can concentrate on the main term in (8). By (7) we can replace ϵ(m) with δ(m) log b and only incur an error which is O(m^{− \frac{1}{8}} ) times the main term. We can ignore this error as it will prove to be negligible. By using m^{\frac{7}{8}} = q/μ_{b} + O(q^{\frac{2}{3}} ) we can reduce the sum to

\frac{b − 1}{ϕ(b − 1)} \frac{1}{\sqrt{2πs_{b}}} ∑_{q<Q} (μ_{b}/q)^{\frac{3}{2}} Σ_{q} + O(1),

with

Σ_{q} = ∑_{\begin{matrix}m≤V \\ |q−μ(m)|<q^{\frac{2}{3}} \end{matrix}} δ(m) exp (−\frac{μ_{b}(q − μ(m))^{2}}{2s_{b}q} ) .

We can identify this as a Riemann sum of an integral and so obtain

\begin{aligned}Σ_{q} & = ∫_{q/μ_{b}−q^{\frac{2}{3}}}^{q/μ_{b}+q^{\frac{2}{3}}} exp (−\frac{μ_{b}(q − μ_{b}x)^{2}}{2s_{b}q} ) dx + O(1) \\ & = \frac{\sqrt{2s_{b}qπ}}{μb^{\frac{3}{2}}} + O(1). \end{aligned}

We have thus shown that

S(X) = \frac{b − 1}{ϕ(b − 1)} ∑_{q<Q} \frac{1}{q} + O(1) = \frac{b − 1}{ϕ(b − 1)}L_{3}(X) + O(1)  (9)

as required to complete the proof.

4 Proof of Theorem 3

We prove Theorem 3 by induction; Theorem 2 is the case j = 1. Now assume that the case j has been proved. If we follow the working in §3, then in place of (9) we obtain

∑_{\begin{matrix}p<X \\ p∈P_{b}^{(j+1)} \end{matrix}} \frac{1}{p} = \frac{b − 1}{ϕ(b − 1)} ∑_{\begin{matrix}p<Y \\ p∈P_{b}^{(j)} \end{matrix}} \frac{1}{p} + O(1)

where Y = log_{b} X. By the inductive hypothesis we therefore have

∑_{\begin{matrix}p<X \\ p∈P_{b}^{(j+1)} \end{matrix}} \frac{1}{p} = (\frac{b − 1}{ϕ(b − 1)})^{j+1} L_{j+3}(X) + O(1)

as required to complete the proof.

5 Acknowledgement

I would like to thank the referee for his suggestions and Christian Elsholtz whose e-mail conversation sparked my interest in this topic.

References

[1] H. Davenport, Multiplicative Number Theory, 2nd edition, revised by H. L. Montgomery, Springer, 1980.

[2] M. Drmota, C. Mauduit and J. Rivat, Primes with an average sum of digits, Compositio Math. 145 (2009), 271–292.

[3] D. Goldston and D. R. Heath-Brown, A note on the difference between consecutive primes, Math. Ann. 266 (1984), 317–320.

[4] D. R. Heath-Brown, The differences between consecutive primes, III, J. London Math. Soc. (2), 20, 177–178.

[5] I. Kátai, On the sum of digits of primes, Acta Math. Acad. Sci. Hungar. 30 (1977), 169–173.

[6] K. Matomäki, Large differences between consecutive primes, Quart. J. Math. 58 (2007), 489–517.

[7] C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math. 171 (2010), 1591–1646.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 11N05, 11N60. Keywords: prime number, sum of digits, Mertens’ theorem.

(Concerned with sequences \underline{A046704}, \underline{A070027}, and \underline{A109981}.)

Received September 16 2011; revised version received December 29 2011. Published in Journal of Integer Sequences, December 30 2011.

Return to Journal of Integer Sequences home page.