The Reciprocal Sum of Even Pseudoprimes

Xuyan Cheng

Department of Computer Science and Engineering

The Ohio State University

Columbus, OH 43201

USA

cheng.2119@osu.edu

Paul Kinlaw College of Arts and Sciences

The University of Maine at Presque Isle

Presque Isle, ME 04769

USA

paulkinlaw1@gmail.com

Duc Nguyen Department of Mathematics

Dickinson College 28N College St. Carlisle, PA 17013

USA

nguyenduc150202@gmail.com

Abstract

A pseudoprime is a composite integer N that mimics the behavior of primes by satisfying the congruence 2^{N} ≡ 2 (mod N) in Fermat’s little theorem. This paper focuses on the subset of even pseudoprimes and obtains an upper bound for the sum of their reciprocals. Our approach combines analytic arguments with computational verification, showing that this sum is less than 0.0059.

1 Introduction

By Fermat’s little theorem, if a is an integer and p is a prime, then a^{p} ≡ a (mod p). However, for each a ≥ 2, the congruence also holds for some composite moduli called base-a (Fermat) pseudoprimes. It is well known that for each a ≥ 2, there are infinitely many pseudoprimes. The base-2 pseudoprimes are also called pseudoprimes for short. We study even pseudoprimes, that is, even numbers N > 2 such that 2^{N} ≡ 2 (mod N). The smallest even pseudoprime is 161038 and Beeger [3] proved that there are infinitely many. The first 1318 even pseudoprimes have been computed by Alekseyev (extending work of Pinch), providing an exhaustive list up to 2 · 10^{15}. This sequence is referenced as \underline{A006935} in the On-Line Encyclopedia of Integer Sequences [5]. Pomerance and Wagstaff [10] later extended the exhaustive search up to 10^{16}, and there are 727 even pseudoprimes in the range 2·10^{15} < N ≤ 10^{16}.

Let E = {161038, 215326, 2568226, …} denote the set of all even pseudoprimes. We prove the following bounds on the sum of reciprocals of even pseudoprimes.

Theorem 1. We have

0.000011 < ∑_{N∈E} \frac{1}{N} < 0.0059.

In particular, this determines the numerical value of the reciprocal sum to two decimal places as 0.00 . . .. It is known [2, 7] that the reciprocal sum of odd pseudoprimes is less than 0.0911. Thus, as a corollary, the sum of reciprocals of all base-2 pseudoprimes is less than 0.1.

2 Notation and preliminary lemmas

Throughout the paper, x denotes a real variable, x_{0} = e^{36}, p denotes a prime variable (with or without subscripts), and log x denotes the natural logarithm. We let Y_{0} = 6.5 · 10^{7}. We also define y_{k} = e^{1.56\sqrt{k}} and z_{k} = e^{k/2}/(2\sqrt{2}) for k ≥ 36. We let a_{1} = 0.4 and a_{2} = 0.48. For a prime p > 2, let the expression ℓ_{2}(p) denote the multiplicative order of 2 mod p, that is, the smallest positive integer such that 2^{ℓ_{2}(p)} ≡ 1 (mod p). In general, if 2^{k} ≡ 1 (mod p) for some integer k ≥ 0, then ℓ_{2}(p) | k. In particular, by Fermat’s little theorem, ℓ_{2}(p) | p − 1.

Note that N = 2n ∈ E if and only if n > 1 and

2^{2n−1} ≡ 1 (mod n).  (1)

In particular, n must be odd. We have the following additional properties of even pseudoprimes.

Lemma 2. For every odd prime p dividing an even pseudoprime N, we have

N ≡ p (mod pℓ_{2}(p)).  (2)

Moreover, ℓ_{2}(p) is odd, p ≡ ±1 (mod 8), and p ≤ N/14.

Remark 3. The congruence Eq. (2) above holds for all pseudoprimes.

Before proving Lemma 2, we note the following corollary, which follows from the fact that any even pseudoprime is of the form 2p_{1} ⋯ p_{r}, where each p_{i} ≡ ±1 (mod 8).

Corollary 4. If N is an even pseudoprime then N ≡ 2 or 14 (mod 16).

Proof of Lemma 2. For an even pseudoprime N = 2n, we have 2^{2n−1} ≡ 1 (mod n) by Eq. (1). Therefore, if p | n, then 2^{2n−1} ≡ 1 (mod p), and thus ℓ_{2}(p) | 2n−1, so that 2n ≡ 1 (mod ℓ_{2}(p)). Therefore, ℓ_{2}(p) is odd. Also, p ≡ 1 (mod ℓ_{2}(p)) by Fermat’s little theorem, so by the last two congruences we have 2n ≡ p (mod ℓ_{2}(p)). Also, 2n ≡ p (mod p) (as both sides are 0 (mod p)). Moreover, gcd(p, ℓ_{2}(p)) = 1 because ℓ_{2}(p) | p − 1. Therefore, N = 2n satisfies the congruence N ≡ p (mod pℓ_{2}(p)).

Note also that N > p because N is composite. Next, note that we have ℓ_{2}(p) | (p − 1)/2 because ℓ_{2}(p) is odd. Therefore, by Euler’s criterion, (2|p) ≡ 2^{(p−1)/2} ≡ 1 (mod p), where (2|p) is the Legendre symbol. Thus (2|p) = 1, so p ≡ ±1 (mod 8). We now show that p ≤ N/14. The congruence 2^{2n−1} ≡ 1 (mod n), which holds for n = N/2, implies that n is odd, so that N = 2mp for some odd m ≥ 1. Moreover, m ≠ 1, for otherwise N = 2p and thus 2^{2p−1} ≡ 1 (mod p), which is impossible since by Fermat’s little theorem, 2^{2p−2} ≡ 1 (mod p). Also, m ≠ 3, 5 because the odd prime factors p of N are of the form ±1 (mod 8). Therefore, m ≥ 7.

We use the fact that pseudoprimes are almost squarefree, in a sense made precise by the following lemma.

Lemma 5. If N is an even pseudoprime and p^{2} | N for a prime p, then p is a Wieferich prime, i.e., 2^{p−1} ≡ 1 (mod p^{2}). In particular, p ≥ 3511.

Proof. The first assertion holds for all pseudoprimes by an argument similar to previous work [2, Lemma 2]. The second assertion follows from the fact that the two smallest Wieferich primes are 1093 and 3511, together with the fact that 1093 ≡ 5 (mod 8), and so by Lemma 2 an even pseudoprime cannot be divisible by 1093.

We also use the following bounds of Dusart [4] on the prime counting function π(x).

Lemma 6. We have

\frac{x}{log x} (1 + \frac{1}{log x}) ≤ π(x) ≤ \frac{x}{log x} (1 + \frac{1.2762}{log x}) ,

where the lower bound holds for all x ≥ 599 and the upper bound holds for all x > 1.

We use partial summation (Abel’s summation identity) [1, Theorem 4.2] to represent sums in terms of integrals.

Lemma 7. Let {a_{n}}_{n≥1} be a sequence of real or complex numbers, and let f have a continuous derivative on the interval [x_{1}, x], 0 < x_{1} < x. Let A(t) = ∑_{n≤t} a_{n}. Then

∑_{x_{1}<n≤x} a_{n}f(n) = A(x)f(x) − A(x_{1})f(x_{1}) − ∫_{x_{1}}^{x} A(t)f′(t) dt.

In particular, if A is a set of natural numbers and we define a_{n} = 1 if n ∈ A and a_{n} = 0 otherwise, then the above equality holds where A is the counting function of the set A.

We also use a result of Nguyen and Pomerance [9, Lemmas 2.9–2.10, Remark 2.1] on the reciprocal sum of integers n > x free of prime factors exceeding a given bound y. (Such numbers are called y-smooth or y-friable.) Let the expression P (n) denote the largest prime factor of n, (n > 1), with the convention P (1) = 1. For 2 ≤ y < x and s > 0, let

ζ(s, y) = ∑_{P (n)≤y} \frac{1}{n^{s}} ,

where the sum is over all positive integers n which are products only of primes less than or equal to y. Note that we have

ζ(s, y) = ∑_{P (n)≤y} \frac{1}{n^{s}} = ∏_{p≤y} (1 + \frac{1}{p^{s}} + \frac{1}{p^{2s}} + ⋯) = ∏_{p≤y} (1 + \frac{1}{p^{s} − 1}) ,

where the first equality holds by unique prime factorization, and the second equality holds by summing the geometric series. Also, let

ζ^{∗}(s, y) = ∑_{P (n)≤y} 2 ∤ n, n squarefree \frac{1}{n^{s}} = ∏_{3≤p≤y} (1 + \frac{1}{p^{s}} )

denote the restriction to y-smooth numbers which are odd and squarefree (that is, not divisible by p^{2} for any prime p). Define

S(x, y) = ∑_{n>x} ; P (n)≤y \frac{1}{n}, S^{∗}(x, y) = ∑_{n>x} 2 ∤ n, n squarefree, P (n)≤y \frac{1}{n}.

Lemma 8 (Nguyen and Pomerance, [9]). For 2 ≤ y < x and 0 < s < 1, we have

S(x, y) ≤ x^{−s}ζ(1 − s, y).  (3)

Let u = log x/ log y and s = log(u log u)/ log y. For u ≥ 3 and s ≤ 1/3, we have

S(x, y) ≤ x^{−s}ζ(1 − s, y) < 25e^{(1+ϵ)u}(u log u)^{−u}(2^{s} − 1)^{−1},  (4)

where ϵ = 2.3 · 10^{−8}.

Remark 9. Following [9, Remark 2.1], for 2 ≤ y < x and 0 < s < 1, we have

S^{∗}(x, y) ≤ x^{−s}ζ^{∗}(1 − s, y).  (5)

We note that more generally, for a given prime p, if the sum S(x, y) is restricted by the assumption that p^{2} ∤ n, then we can replace the factor 1 + 1/(p^{s} − 1) with 1 + 1/p^{s} in the product defining ζ(s, y). Similarly, given the stronger restriction p ∤ n, we can remove the factor 1 + 1/(p^{s} − 1) in the product defining ζ(s, y).

For fixed real numbers 0 ≤ a < b ≤ 1, we define Q_{a,b} = {p > 2 : 2 ∤ ℓ_{2}(p) and p^{a} < ℓ_{2}(p) ≤ p^{b}}. We let Q_{a,b}(x) = |Q_{a,b} ∩ [1, x]|. Recall that a_{1} = 0.4 and a_{2} = 0.48. We use the following modification of previous work [7, Inequality (8)].

Lemma 10. We have

Q_{0,a_{1}}(x) < Mx^{2a_{1}}

for all x ≥ 0, where M = 0.00754. Moreover, Q_{a_{1},a_{2}}(x) < Mx^{2a_{2}} for all x ≥ 337.

Proof. We prove the claim for Q_{0,a_{1}}, noting that an analogous argument deals with the case of Q_{a_{1},a_{2}}. (For x > e^{23}, we use the trivial inequality Q_{a_{1},a_{2}} ≤ Q_{0,a_{2}}.) We find by a computer check in Pari/GP [6] that the claim holds for all x ≤ e^{23}, Q_{0,a_{1}}(e^{23}) = 638, and

∏_{p∈Q_{0,a_{1}}} ; p≤e^{23} p > e^{D}

where D = 12895. Let x > e^{23}. If p ≤ x and p ∈ Q_{0,a_{1}}, then p | 2^{m} − 1 for some odd m > 1 such that m < p^{a_{1}} ≤ x^{a_{1}}, so that

∏_{p∈Q_{0,a_{1}}} ; p≤x p | ∏_{m≤x^{a_{1}}} ; 2 ∤ m(2^{m} − 1).

Therefore,

∏_{p∈Q_{0,a_{1}}} ; p≤x p ≤ ∏_{m≤x^{a_{1}}} ; 2 ∤ m(2^{m} − 1)

≤ exp (log 2 ∑_{m≤x^{a_{1}}} ; 2 ∤ m m) ≤ exp (log 2 (\frac{x^{a_{1}} + 1}{2})^{2})

≤ exp (\frac{log 2}{4}(1.00021)x^{2a_{1}}) ≤ exp(0.17333x^{2a_{1}}).

(6)

Here, we used the formula 1 + 3 + 5 + ⋯ + (2j − 1) = j^{2} for the sum of the first j odd numbers, with j = ⌊(x^{a_{1}} + 1)/2⌋. Also,

∏_{p∈Q_{0,a_{1}}} ; p≤x p = ∏_{p∈Q_{0,a_{1}}} ; p≤e^{23} p ∏_{p∈Q_{0,a_{1}}} ; e^{23}<p≤x p > e^{D}(e^{23})^{Q_{0,a_{1}}(x)−Q_{0,a_{1}}(e^{23})},

where the lower bound on the rightmost product is obtained by replacing each factor p with e^{23}. We therefore have

Q_{0,a_{1}}(x) ≤ Q_{0,a_{1}}(e^{23}) − D/23 + 0.17333x^{2a_{1}}/23 = 638 − 12895/23 + 0.17333x^{2a_{1}}/23

for all x ≥ e^{23}. Simplifying, we complete the proof of Lemma 10.

3 The reciprocal sum of even pseudoprimes

To bound the reciprocal sum we split E into two ranges. The small range consists of N ∈ E such that N ≤ 10^{16}. Using the exhaustive list for N ≤ 2 · 10^{15}, and noting that there are 727 terms in the interval (2 · 10^{15}, 10^{16}], contributing less than 727/(2 · 10^{15}) to the reciprocal sum, we obtain

∑_{N∈E} ; N≤10^{16} \frac{1}{N} = 0.0000118853 ….  (7)

We are grateful to Mark Royer for computing this sum to high precision using Python.

The large range consists of N ∈ E such that N > x_{0}, where x_{0} = e^{36}. Note that 10^{16} > e^{36}, so there is no gap between the small and large ranges. Recall that Y_{0} = 6.5·10^{7}, y_{k} = e^{1.56\sqrt{k}}, and z_{k} = e^{k/2}/(2\sqrt{2}), k ≥ 36. We determine an upper bound by splitting E ∩ (e^{36}, ∞) into intervals (e^{k}, e^{k+1}), k ≥ 36. First, we partition E into five subsets depending on the relative sizes of p = P (N) = P (n) and ℓ_{2}(p) as follows:

A_{1} = {N ∈ E : p ≤ y_{⌊log N⌋}}
A_{2} = {N ∈ E : e^{36} < N ≤ e^{130}, y_{⌊log N⌋} < p ≤ min(Y_{0}, z_{k})}
A_{3} = {N ∈ E \ A_{2} : p > y_{⌊log N⌋}, and p ∈ Q_{0,a_{1}}}
A_{4} = {N ∈ E \ A_{2} : p > y_{⌊log N⌋}, and p ∈ Q_{a_{1},a_{2}}}
A_{5} = {N ∈ E \ A_{2} : p > y_{⌊log N⌋}, and p ∈ Q_{a_{2},1}}.

We further partition A_{2} into the cases 36 ≤ k ≤ 38, y_{k} < p ≤ z_{k} and 39 ≤ k ≤ 130, y_{k} < p ≤ Y_{0}. For 2 ≤ i ≤ 5 we further partition A_{i} into the cases 39 ≤ k ≤ 130, Y_{0} < p ≤ z_{k}, k ≥ 131, y_{k} < p ≤ z_{k}, and k ≥ 36, p > z_{k}. This partition is inspired by previous work [8, Theorem 9.11], [7, Theorem 1] on the reciprocal sum of odd pseudoprimes.

We first bound the sum over N = 2n ∈ A_{1} ∩ (e^{k}, e^{k+1}), k ≥ 36. Recall that n is odd, and by Lemma 2, n is not divisible by any prime p such that ℓ_{2}(p) is even. Moreover, by Lemma 5, n is not divisible by p^{2} for any prime p < 3511. Using Remark 9, we find that

∑_{N=2n∈A_{1}} ; N>x_{0} \frac{1}{N} = \frac{1}{2} ∑_{2n∈A_{1}} ; n> \frac{x_{0}}{2} \frac{1}{n} = \frac{1}{2} ∑_{k≥36} ∑_{2n∈A_{1}} ; \frac{e^{k}}{2} <n≤ \frac{e^{k+1}}{2} \frac{1}{n} < \frac{0.004024 + 0.002251}{2} < 0.003138.

Specifically, the term 0.004024 comes from the range 36 ≤ k ≤ 120 using Eq. (3) and Remark 9 with s = log(e^{0.8}u log u)/ log y, and the term 0.002251 comes from the range k > 120 using Eq. (4) and Remark 9.

We now turn to the cases A_{i}, i = 2, 3, 4, 5. By Lemma 2 and Corollary 4, we have

∑_{N∈E\A_{1}} ; N>x_{0} \frac{1}{N} ≤ ∑_{k≥36} ∑_{p>y_{k}} ; 2 ∤ ℓ_{2}(p) ∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N≡±2 (mod 16) \\ N>p \end{matrix}} \frac{1}{N} .  (8)

We split this sum into cases depending on the values of k and p.

The condition N > p is redundant since N is even (and composite), however, it is useful in the following argument. If we set aside the condition N ≡ ±2 (mod 16), we obtain an estimate that works well for large values of p, specifically p > z_{k}. The counting function

g_{p}(t) := |{N ≤ t : N ≡ p (mod pℓ_{2}(p)) and N > p}|

of numbers exceeding p that are congruent to p mod pℓ_{2}(p) satisfies

g_{p}(t) = ⌊\frac{t − p}{pℓ_{2}(p)}⌋ , (t ≥ p).  (9)

Thus by partial summation (Lemma 7) we have

\begin{aligned}∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N>p \end{matrix}} \frac{1}{N} & = \frac{g_{p}(e^{k+1})}{e^{k+1}} − \frac{g_{p}(e^{k})}{e^{k}} + ∫_{e^{k}}^{e^{k+1}} \frac{g_{p}(t)}{t^{2}} dt \\ & ≤ \frac{g_{p}(e^{k+1})}{e^{k+1}} − \frac{g_{p}(e^{k})}{e^{k}} + ∫_{e^{k}}^{e^{k+1}} \frac{1}{t^{2}} (\frac{t − p}{pℓ_{2}(p)}) dt. \end{aligned}

Integrating directly, we have

∫_{e^{k}}^{e^{k+1}} \frac{1}{t^{2}} (\frac{t − p}{pℓ_{2}(p)}) dt = \frac{1}{pℓ_{2}(p)} + \frac{e^{−(k+1)} − e^{−k}}{ℓ_{2}(p)} .

This allows us to obtain the following upper bound.

F_{p}(k) := ∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N>p \end{matrix}} \frac{1}{N} ≤ \frac{1}{e^{k+1}} ⌊\frac{e^{k+1} − p}{pℓ_{2}(p)}⌋ − \frac{1}{e^{k}} ⌊\frac{e^{k} − p}{pℓ_{2}(p)}⌋ + \frac{1}{pℓ_{2}(p)} + \frac{e^{−(k+1)} − e^{−k}}{ℓ_{2}(p)} .

Removing the second and fourth terms, which are nonpositive, we obtain the following proposition.

Proposition 11. For odd primes p, we have

F_{p}(k) = ∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N>p \end{matrix}} \frac{1}{N} ≤ \frac{2}{pℓ_{2}(p)}.

Next, we obtain an improvement when p ≤ z_{k} := e^{k/2}/\sqrt{8} by using the condition N ≡ 2 or 14 (mod 16). We also have N ≡ p (mod pℓ_{2}(p)), and additionally, gcd(pℓ_{2}(p), 16) = 1 when p and ℓ_{2}(p) are odd. Thus by the Chinese remainder theorem, N lies within two residue classes modulo 16pℓ_{2}(p). The counting function is therefore

f_{p}(t) := |\{N ≤ t : N ≡ p (mod pℓ_{2}(p)), N ≡ ±2 (mod 16)\}| ≤ 2 (\frac{t}{16pℓ_{2}(p)} + 1) .

Also,

f_{p}(t) ≥ 2 ⌊\frac{t}{16pℓ_{2}(p)}⌋ .

Using the upper bound for f_{p}(t) and proceeding as above, we have

\begin{aligned}∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N≡±2 (mod 16) \end{matrix}} \frac{1}{N} & = \frac{f_{p}(e^{k+1})}{e^{k+1}} − \frac{f_{p}(e^{k})}{e^{k}} + ∫_{e^{k}}^{e^{k+1}} \frac{f_{p}(t)}{t^{2}} dt \\ & ≤ \frac{1}{4pℓ_{2}(p)} + \frac{2}{e^{k}} − \frac{f_{p}(e^{k})}{e^{k}}. \end{aligned}

Now f_{p}(e^{k}) ≥ 2 when 16pℓ_{2}(p) ≤ e^{k}. In particular, with ℓ_{2}(p) odd, we have ℓ_{2}(p) ≤ (p−1)/2, so the inequality 16pℓ_{2}(p) ≤ e^{k} holds for p ≤ z_{k}.

On the other hand, we have

f_{p}(t) ≥ 2 ⌊\frac{t}{16pℓ_{2}(p)}⌋ ≥ 2 (\frac{t}{16pℓ_{2}(p)} − 1) .

This gives

∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N≡±2 (mod 16) \end{matrix}} \frac{1}{N} ≤ \frac{1}{8pℓ_{2}(p)} + \frac{4}{e^{k}} .

In the case of A_{3} and A_{4}, for p ≤ z_{k}, we also have ℓ_{2}(p) < p^{0.4} and ℓ_{2}(p) < p^{0.48}, respectively.

We summarize these bounds in the following Proposition.

Proposition 12. If p and ℓ_{2}(p) are odd, then we have

∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N≡±2 (mod 16) \end{matrix}} \frac{1}{N} ≤ \frac{1}{4pℓ_{2}(p)}

whenever 16pℓ_{2}(p) ≤ e^{k}, and in particular when p ≤ z_{k}. Moreover,

∑_{\begin{matrix}e^{k}<N≤e^{k+1} \\ N≡p (mod pℓ_{2}(p)) \\ N≡±2 (mod 16) \end{matrix}} \frac{1}{N} ≤ \frac{1/8 + 4e^{−k}pℓ_{2}(p)}{pℓ_{2}(p)}.

When p ≤ z_{k} and ℓ_{2}(p) < p^{0.4} (respectively, ℓ_{2}(p) < p^{0.48}), this is bounded above by c_{k}/(pℓ_{2}(p)) (respectively, d_{k}/(pℓ_{2}(p))) where c_{k} = 1/8 + (4/8^{0.7})e^{−0.3k} and d_{k} = 1/8 + (4/8^{0.74})e^{−0.26k}.

We now consider A_{2}. We apply Proposition 12 to bound

∑_{N∈A_{2}} ; N>x_{0} \frac{1}{N} ≤ ∑_{36≤k≤38} ∑_{y_{k}<p≤z_{k}} ; 2 ∤ ℓ_{2}(p) \frac{1}{4pℓ_{2}(p)} + ∑_{39≤k≤130} ∑_{y_{k}<p≤Y_{0}} ; 2 ∤ ℓ_{2}(p) \frac{1}{4pℓ_{2}(p)} < 0.000070

by direct computation.

We next consider A_{3}. Note that p | 2^{ℓ_{2}(p)} − 1, so that ℓ_{2}(p) > log p/ log 2. We therefore have

∑_{y_{k}<p≤z_{k}} ; p∈Q_{0,a_{1}} \frac{1}{pℓ_{2}(p)} ≤ log 2 ∑_{p>y_{k}} ; p∈Q_{0,a_{1}} \frac{1}{p log p}.

By partial summation (Lemma 7), the rightmost sum above is equal to

log 2 (−\frac{Q_{0,a_{1}}(y_{k})}{y_{k} log y_{k}} + ∫_{y_{k}}^{∞} \frac{(1 + log t)Q_{0,a_{1}}(t)}{t^{2} log^{2} t}dt) .

By Lemma 10, Q_{0,a_{1}}(t) ≤ Mt^{0.8} for all t > 0, where M = 0.00754. We therefore have

∑_{p>y_{k}} ; p∈Q_{0,a_{1}} \frac{1}{pℓ_{2}(p)} ≤ M log 2 ∫_{y_{k}}^{∞} \frac{1 + log t}{t^{2−2a_{1}} log^{2} t}dt

= M log 2 (−2a_{1}Ei((2a_{1} − 1) log y_{k}) + \frac{y_{k}^{2a_{1}−1}}{log y_{k}} ) ,

(10)

where

Ei(x) = ∫_{−∞}^{x} \frac{e^{t}}{t} dt

is the exponential integral function. An analogous bound holds with Y_{0} in place of y_{k}. Similarly, for primes p > z_{k}, we may apply Proposition 11. Let

B_{3}(z) := M log 2 (−2a_{1}Ei((2a_{1} − 1) log z) + \frac{z^{2a_{1}−1}}{log z} ) .

We have

∑_{N∈A_{3}} ; N>x_{0} \frac{1}{N} ≤ ∑_{39≤k≤130} c_{k}B_{3}(Y_{0}) + ∑_{k≥131} c_{k}B_{3}(y_{k}) + ∑_{k≥36} 2B_{3}(z_{k}).

We next consider A_{4}. By Lemma 10 we have Q_{a_{1},a_{2}}(x) ≤ Mx^{2a_{2}} for all x ≥ 337, where M = 0.00754. Since p ∈ Q_{a_{1},a_{2}}, we also have ℓ_{2}(p) > p^{a_{1}}. Therefore,

∑_{y_{k}<p≤z_{k}} ; p∈Q_{a_{1},a_{2}} \frac{1}{pℓ_{2}(p)} ≤ ∑_{p>y_{k}} ; p∈Q_{a_{1},a_{2}} \frac{1}{p^{1+a_{1}}} .

By partial summation (Lemma 7), the rightmost sum above is equal to

\begin{aligned}−\frac{Q_{a_{1},a_{2}}(y_{k})}{y_{k}^{1+a_{1}}} + (1 + a_{1}) ∫_{y_{k}}^{∞} \frac{Q_{a_{1},a_{2}}(t)}{t^{2+a_{1}}}dt & ≤ (1 + a_{1})M ∫_{y_{k}}^{∞} \frac{dt}{t^{2+a_{1}−2a_{2}}} \\ & = \frac{(1 + a_{1})M}{(1 + a_{1} − 2a_{2})y_{k}^{1+a_{1}−2a_{2}}} . \end{aligned}  (11)

An analogous bound holds with Y_{0} in place of y_{k}, and with z_{k} in place of y_{k}. Let B_{4}(z) := (1 + a_{1})M/((1 + a_{1} − 2a_{2})z^{1+a_{1}−2a_{2}}). By Propositions 11 and 12, we have

∑_{N∈A_{4}} ; N>x_{0} \frac{1}{N} ≤ ∑_{39≤k≤130} d_{k}B_{4}(Y_{0}) + ∑_{k≥131} d_{k}B_{4}(y_{k}) + ∑_{k≥36} 2B_{4}(z_{k}).

For A_{5}, we have by partial summation (Lemma 7) with f(t) = 1/t^{1+a_{2}} that

∑_{y_{k}<p≤z_{k}} \frac{1}{pℓ_{2}(p)} ≤ ∑_{p>y_{k}} \frac{1}{p^{1+a_{2}}} = −\frac{π(y_{k})}{y_{k}^{1+a_{2}}} + (1 + a_{2}) ∫_{y_{k}}^{∞} \frac{π(t)}{t^{2+a_{2}}} dt.  (12)

By Lemma 6, this is bounded above by

− \frac{1}{y_{k}^{a_{2}} log y_{k}} − \frac{1}{y_{k}^{a_{2}} log^{2} y_{k}} + (1 + a_{2}) ∫_{y_{k}}^{∞} (\frac{1}{log t} + \frac{1.2762}{log^{2} t}) \frac{dt}{t^{1+a_{2}}}  (13)

and the integral evaluates to

−Ei(−a_{2} log y_{k}) + 1.2762 (a_{2}Ei(−a_{2} log y_{k}) + \frac{1}{y_{k}^{a_{2}} log y_{k}} ) .

As before, an analogous bound holds with Y_{0} in place of y_{k}, and with z_{k} in place of y_{k}. Let

B_{5}(z) := −\frac{1 + 1/ log z}{z^{a_{2}} log z} + (1 + a_{2}) ∫_{z}^{∞} (\frac{1}{log t} + \frac{1.2762}{log^{2} t}) \frac{dt}{t^{1+a_{2}}} .

Proceeding as we did with A_{4}, we use Propositions 11 and 12 to bound the contribution to the reciprocal sum as

∑_{N∈A_{5}} ; N>x_{0} \frac{1}{N} ≤ ∑_{39≤k≤130} 0.25B_{5}(Y_{0}) + ∑_{k≥131} 0.25B_{5}(y_{k}) + ∑_{k≥36} 2B_{5}(z_{k}).

Summing the contributions from the small range along with the five cases in the large range k ≥ 36, we obtain the following upper bound:

∑_{N∈E} \frac{1}{N} ≤ 0.000012 + 0.003138 + 0.000070

+ ∑_{39≤k≤130}(c_{k}B_{3}(Y_{0}) + d_{k}B_{4}(Y_{0}) + 0.25B_{5}(Y_{0}))

+ ∑_{k≥131}(c_{k}B_{3}(y_{k}) + d_{k}B_{4}(y_{k}) + 0.25B_{5}(y_{k}))

+ ∑_{k≥36}(2B_{3}(z_{k}) + 2B_{4}(z_{k}) + 2B_{5}(z_{k}))

< 0.000012 + 0.003138 + 0.000070 + 0.000925 + 0.000535 + 0.001185 < 0.0059.

This completes the proof of Theorem 1.

4 Acknowledgments

We thank Linh Hoang for assistance and feedback, as well as Mark Royer for computing the sum in Eq. (7) to high precision. We also thank the anonymous referee for helpful feedback.

References

[1] Tom M. Apostol, Introduction to Analytic Number Theory, Springer Science & Business Media, 2013.

[2] J. Bayless and P. Kinlaw, Explicit bounds for the sum of reciprocals of pseudoprimes and Carmichael numbers, J. Integer Sequences 20 (2017), Article 17.6.4.

[3] N. G. W. H. Beeger, On even numbers m dividing 2^{m} − 2, Amer. Math. Monthly 58 (1951), 553–555.

[4] P. Dusart, Explicit estimates of some functions over primes, Ramanujan J. 45 (2018), 227–251.

[5] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis. org, 2026.

[6] The PARI Group, Pari/gp version 2.13.3, http://pari.math.u-bordeaux.fr/, 2022.

[7] P. Kinlaw, The reciprocal sums of pseudoprimes and Carmichael numbers, Math. Comp., to appear.

[8] Jean-Marie De Koninck and Florian Luca, Analytic Number Theory: Exploring the Anatomy of Integers, Vol. 134 of Graduate Studies in Mathematics, Amer. Math. Society, 2023.

[9] H. Nguyen and C. Pomerance, The reciprocal sum of the amicable numbers, Math. Comp. 88 (2019), 1503–1526.

[10] C. Pomerance and S. Wagstaff, Some thoughts on pseudoprimes, Bull. Cl. Sci. Math. Nat. Sci. Math. 46 (2021), 53–72.

2020 Mathematics Subject Classification: Primary 11N25; Secondary 11N37. Keywords: pseudoprime, smooth number.

(Concerned with sequence \underline{A006935}.)

Received October 24 2024; revised versions received October 25 2024; November 4 2025; December 19 2025. Published in Journal of Integer Sequences, January 26 2026.

Return to Journal of Integer Sequences home page.