Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers

Jonathan Bayless and Paul Kinlaw Husson University 1 College Circle Bangor, ME 04401 USA

                      baylessj@husson.edu
                      kinlawp@husson.edu

Abstract

From a 1956 paper of Erdős, we know that the base-two pseudoprimes and the Carmichael numbers both have a convergent sum of reciprocals. We prove that the values of these sums are less than 33 and 28, respectively.

1 Introduction

By Fermat’s little theorem, if p is a prime number then for all a ∈ ℤ we have a^{p} ≡ a (mod p). However, a number p satisfying this property need not be a prime. For all a ∈ ℤ, a base-a Fermat pseudoprime (or briefly, an a-pseudoprime) is a composite number n such that gcd(a, n) = 1 and a^{n} ≡ a (mod n). A Carmichael number is an odd composite number n for which a^{n} ≡ a (mod n) for all integers a, and so is an a-pseudoprime for all a with gcd(a, n) = 1.

Let 𝒫_{2} = {341, 561, 645, 1105, …} be the set of 2-pseudoprimes, also called Poulet or Sarrus numbers, and let P_{2}(x) = |{n ∈ 𝒫_{2} : n ≤ x}| be the corresponding counting function. Let 𝒞 = {561, 1105, 1729, …} be the set of Carmichael numbers and write its counting function as C(x) = |{n ∈ 𝒞 : n ≤ x}|. Erdős [11] proved that for sufficiently large x, we have

P_{2}(x) < x/ exp(c_{1}\sqrt{log x log log x})

and

C(x) < x/ exp (\frac{c_{2} log x log log log x}{log log x})

for constants c_{1}, c_{2} > 0. This implies that both sets have asymptotic density zero, as well as the stronger statement that both sets have a bounded sum of reciprocals. Pomerance [18] improved these bounds, showing that

P_{2}(x) < x/ exp (\frac{log x log log log x}{2 log log x})

for all sufficiently large x, and that the constant c_{2} in the above bound on C(x) may be taken as 1.

In the other direction, it is well known that there are infinitely many pseudoprimes with respect to a given base. In 1994 Alford, Granville and Pomerance [1] proved that there are infinitely many Carmichael numbers. In particular, they proved that C(x) > x^{2/7} for sufficiently large x. Their work has since been improved by Harman [13] to show that for large x, the inequality C(x) > x^{α} holds for some constant α > 1/3.

In this paper we determine explicit upper and lower bounds for the sum of reciprocals of 2-pseudoprimes, as well as for the sum of reciprocals of Carmichael numbers. This extends previous work [4, 5, 3, 14] on reciprocal sums. See [5] for a discussion of reciprocal sums and their importance in number theory.

2 Preliminary lemmas

We state several preliminary lemmas. Throughout the paper m, n and k denote positive integers, p denotes a prime number, π(x) is the prime counting function, log x denotes the natural logarithm and P (n) denotes the largest prime factor of n. Put x_{0} = exp(100) and y_{0} = exp(10). We begin with Korselt’s criterion [7, Thm. 3.4.6] which provides a useful characterization of Carmichael numbers.

Lemma 1 (Korselt’s Criterion). A positive integer n is a Carmichael number if and only if it is composite, squarefree, and for each prime p|n we have p − 1|n − 1.

It follows from Korselt’s criterion that Carmichael numbers are odd and have at least three different prime factors.

The following lemma involves certain divisibility properties possessed by all 2-pseudoprimes. In particular, it shows that if a 2-pseudoprime n is divisible by p^{2} for a prime p, then p must be a Wieferich prime, that is,

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

It follows that p is greater than or equal to 1093, the smallest Wieferich prime, see [7, p. 31].

Lemma 2. Let n be a 2-pseudoprime. If p^{2}|n then p is a Wieferich prime. Furthermore, if 7|n then n ≡ 1 (mod 3).

Proof. Suppose that p^{2}|n and let k be the order of 2 in (ℤ/p^{2}ℤ)^{×}. Thus k|φ(p^{2}) = p(p − 1). Now 2^{n−1} ≡ 1 (mod n), so 2^{n−1} ≡ 1 (mod p^{2}), and thus k|n − 1, so k does not divide p. Thus k|p − 1, so that 2^{p−1} ≡ 1 (mod p^{2}). This completes the proof of the first assertion.

For the second assertion, we have 2^{n−1} ≡ 1 (mod n), so if 7|n then 2^{n−1} ≡ 1 (mod 7). The order of 2 modulo 7 is 3, so 3|n − 1.

We will also use explicit versions of several classical theorems. The following modification of [2, Thm. 3.2] gives fairly sharp explicit bounds on the partial sums of the harmonic series.

Lemma 3. For all x ≥ 1,

|∑_{n≤x} \frac{1}{n} − (log x + γ)| < \frac{1}{x}

where γ = 0.5772156649 … denotes Euler’s constant.

We will also use the following modification of [3, Lem. 6.2] to bound the sum of reciprocals of numbers in a certain interval and residue class.

Lemma 4. Let a ∈ ℤ and d = 2 ∏_{i=2}^{9} p_{i}^{2}, where p_{i} denotes the i-th prime number. We have

∑_{n≡a(d)} ; 10^{19}<n≤x_{0} \frac{1}{n} < \frac{56.25587}{d}.

Proof. Let b = (10^{19} − d + 1)/d and c = x_{0}/d. Without loss of generality, we may assume that a ∈ {0, …, d − 1}. By Lemma 3 we have

∑_{b<k≤c} \frac{1}{dk + a} ≤ \frac{1}{d} (100 − log(10^{19} − d + 1) + \frac{1}{c} + \frac{1}{b}) < \frac{56.25587}{d}.

We will use Dusart’s bounds [10, Thm. 5.6] on the sum of reciprocals of prime numbers up to x.

Lemma 5. For all x ≥ 2278383, we have

|∑_{p≤x} \frac{1}{p} − (log log x + B)| < \frac{0.2}{log^{3} x},

where B = 0.2614972128476 … denotes the Mertens constant.

We will also use Dusart’s bounds [10, Cor. 5.2 & Thm. 5.9].

Lemma 6. For all x > 1 we have

π(x) ≤ \frac{x}{log x} (1 + \frac{1}{log x} + \frac{2.53816}{log^{2} x}) ,

and for all x ≥ 599 we have

π(x) ≥ \frac{x}{log x} (1 + \frac{1}{log x}) .

Lemma 7. For all x ≥ 2278382, we have

∏_{p≤x} (1 − \frac{1}{p}) ≥ \frac{exp(−γ)}{log x} (1 − \frac{0.2}{log^{3} x}) .

We will also use the following result [9, Lem. 9.6].

Lemma 8. Let f be a multiplicative function such that f(n) ≥ 0 for all n, and such that there exist constants A and B such that for all x > 1, we have

∑_{p≤x} f(p) log p ≤ Ax  and  ∑_{p} ∑_{α≥2} \frac{f (p^{α})}{p^{α}} log p^{α} ≤ B.  (1)

Then, for x > 1, we have

∑_{n≤x} f(n) ≤ (A + B + 1)\frac{x}{log x} ∑_{n≤x} \frac{f(n)}{n}.

The following lemma makes the implied constants in [9, Lem. 9.7] explicit and modifies [3, Lem. 2.4].

Lemma 9. Let f be a multiplicative function such that 0 ≤ f(p^{α}) ≤ exp (\frac{2α}{3}) for all primes p and integers α ≥ 1, and such that f (p^{α}) = p^{2α/(3 log y)} for all p ≤ y. Then for all x ≥ x_{0} and y ≥ y_{0}, we have

∑_{n≤x} f(n) ≤ 9.68765388x ∏_{p≤x} ((1 − \frac{1}{p}) ∑_{α≥0} \frac{f(p^{α})}{p^{α}}) .

Proof. We wish to apply Lemma 8, and so we first establish values of A and B to use in inequality (1) above. We have

∑_{p≤x} f(p) log p ≤ exp(2/3)θ(x) ≤ 1.00000075 exp(2/3)x ≤ 1.94773551x,  (2)

using the bound θ(x) < 1.00000075x for all x > 0 [17, Cor. 2]. We also have y ≥ y_{0} and

f (p^{α}) = p^{2α/(3 log y)}

whenever p ≤ y. For brevity, let g(t) = (f(t) · log t)/t. We have

∑_{p} ∑_{α≥2} g (p^{α}) = ∑_{p<y_{0}} ∑_{α≥2} g (p^{α}) + ∑_{p>y_{0}} ∑_{α≥2} g (p^{α}) .

Starting to bound the sum with p = 2, observe that

\begin{aligned}∑_{α≥2} g (2^{α}) & ≤ ∑_{α≥2} \frac{α(log 2) · 2^{α/15}}{2^{α}} = log 2 ∑_{α≥2} α (2^{1/15−1})^{α} \\ & < 1.23661725. \end{aligned}

Here we used the fact that

∑_{α≥2} αr^{α−1} = \frac{2r − r^{2}}{(1 − r)^{2}}

for |r| < 1. By similar reasoning,

∑_{3≤p<y_{0}} ∑_{α≥2} g (p^{α}) < 1.25448156.

Let h(t) = (2 − e^{2/3}/t)(log t)/(t − e^{2/3})^{2}. By partial summation we have

∑_{p>y_{0}} ∑_{α≥2} g (p^{α}) ≤ e^{4/3} ∑_{p>y_{0}} \frac{(2 − e^{2/3}/p) log p}{(p − e^{2/3})^{2}}

= e^{4/3} (−h(y_{0})π(y_{0}) − ∫_{y_{0}}^{∞} π(t)h′(t) dt)

< e^{4/3} (−h(y_{0})π(y_{0}) + ∫_{y_{0}}^{∞} \frac{π(t) · 2(2 − \frac{e^{2/3}}{t}) log t dt}{(t − e^{2/3})^{3}})

< e^{4/3} (−h(y_{0})π(y_{0}) + ∫_{y_{0}}^{∞} \frac{2t · 1.1253816(2 − \frac{e^{2/3}}{t}) dt}{(t − e^{2/3})^{3}})

= e^{4/3} (−0.00010166 + \frac{1.1253816 · (4e^{10} − 3e^{2/3})}{(e^{2/3} − e^{10})^{2}})

< 0.00038973.

Here we used Lemma 6. Furthermore, for all x ≥ x_{0} we have

1.781072775 ∏_{p≤x} (1 − \frac{1}{p}) ≥ \frac{1}{log x}.

by Lemma 7. Applying Lemma 8 with A = 1.94773551 and B = 2.49148854, and noting that A + B + 1 = 5.43922405 and 5.43922405 · 1.781072775 < 9.68765388, we complete the proof of the lemma.

We now prove the following explicit upper bound on de Bruijn’s function Ψ(x, y), defined as the number of numbers up to x that are y-smooth (that is, free of prime factors exceeding y).

Lemma 10. For all x ≥ x_{0} and y ≥ y_{0}, we have

Ψ(x, y) ≤ 31.928253x^{1−1/(2 log y)}.

Proof. We follow [9, Thm. 9.5]. By Rankin’s method, if β > 0, then

Ψ(x, y) ≤ x^{3/4} + ∑_{n≤x} (\frac{n}{x^{3/4}} )^{β} χ_{y}(n),  (3)

where χ_{y}(n) = 1 if P (n) ≤ y and χ_{y}(n) = 0 if P (n) > y. Set β = \frac{2}{3 log y}. By Lemma 9, we have that

∑_{n≤x} n^{β}χ_{y}(n) ≤ 9.68765388x ∏_{p≤y} ((1 − p^{−1}) ∑_{α≥0} p^{α(β−1)}) .  (4)

Now, for any given value of p,

(1 − \frac{1}{p}) ∑_{α≥0} p^{α(β−1)} = (1 − \frac{1}{p}) \frac{1}{1 − p^{β−1}} = \frac{p − 1}{p − p^{β}} = 1 + \frac{p^{β} − 1}{p − p^{β}}.

For p ≤ 13, the product contributes a factor less than 1.18817106 to the product in inequality (4). Bounding this second term for p > 13, we see that

\frac{p^{β} − 1}{p − p^{β}} = \frac{p}{p − p^{β}} · \frac{p^{β} − 1}{p} < 1.07648742 · \frac{p^{β} − 1}{p}

since for p ≥ 17,

\frac{p}{p − p^{β}} ≤ (\frac{17}{17 − 17^{1/15}} ) < 1.07648742.

For 0 < t ≤ \frac{2}{3} we have e^{t} − 1 ≤ 1.4216011t and therefore we may bound

∑_{p=17}^{y} 1.07648742 · \frac{p^{β} − 1}{p} = ∑_{p=17}^{y} 1.07648742 · \frac{exp (log p^{β}) − 1}{p}

≤ 1.4216011 · 1.07648742β ∑_{p≤y} \frac{log p}{p}

< 1.4216011 · 1.07648742β log y.

Here we used Rosser and Schoenfeld’s bound (3.23), [19, p. 70],

∑_{p≤y} \frac{log p}{p} < log y − 1.3325 + \frac{1}{log y} < log y

for y ≥ 32. We therefore have inequality (4) bounded above by

9.68765388 · 1.18817106e^{1.4216011·1.07648742β log y} ≤ 31.9282527.

Using this in inequality (3) for x ≥ x_{0} gives the bound

Ψ(x, y) ≤ x^{3/4} + 31.9282527x^{1−1/(2 log y)} ≤ 31.928253x^{1−1/(2 log y)}.

3 The sum of reciprocals of base-two pseudoprimes

We prove explicit bounds on the sum of reciprocals of 2-pseudoprimes by expanding Luca and De Koninck’s proof [9, Prop. 9.11] of the following result.

Proposition 11. For all c < 1/(2\sqrt{2}) we have P_{2}(x) ≪ x exp (−c\sqrt{log x}).

By partial summation, it follows that the sum of reciprocals is convergent.

Theorem 12. The sum of the reciprocals of base-two pseudoprimes satisfies

0.0152608 < ∑_{n∈𝒫_{2}} \frac{1}{n} < 33.

To prove Theorem 12 we split the 2-pseudoprimes into three ranges.

3.1 The small range

We first compute the reciprocal sum over n ≤ 10^{19}. Feitsma [12] has computed an exhaustive list of all 2-pseudoprimes n ≤ 10^{19}. We use this information to directly compute the reciprocal sum from the 2-pseudoprimes n ≤ 10^{12} to seven decimal places as

∑_{n∈𝒫_{2}} ; n≤10^{12} \frac{1}{n} = 0.0152608 ….

For each k = 12, …, 18, the contribution to the reciprocal sum from 2-pseudoprimes n such that 10^{k} < n ≤ 10^{k+1} is bounded above by the number of such n times 10^{−k}. We thus obtain

∑_{n∈𝒫_{2}} ; n≤10^{19} \frac{1}{n} ≤ 0.0152612.

3.2 The middle range

We now bound the reciprocal sum over n such that 10^{19} < n ≤ x_{0}. By Lemma 2, all 2pseudoprimes are odd and not divisible by the square of any prime p < 1093. Therefore, they must lie in one of

D = ∏_{i=2}^{9}(p_{i}^{2} − 1)

residue classes modulo d, where d is as defined in Lemma 4. Also by Lemma 2, no 2pseudoprime is congruent to 0 or 14 modulo 21. Therefore we may rule out 30 more residue classes modulo 3^{2}7^{2}. Thus 2-pseudoprimes must lie in one of

D′ = 354 · 24 · 120 · 168 · 288 · 360 · 528

residue classes modulo d. Therefore by Lemma 4, we have

∑_{n∈𝒫} ; 10^{19}<n≤x_{0} \frac{1}{n} < \frac{56.25587D′}{d} < 21.196317.

We may also remove the contribution to the sum from prime numbers. By Lemma 5, we have

∑_{10^{19}<p≤x_{0}} \frac{1}{p} > 0.826696.

The sum in the middle range is therefore bounded above by

21.196317 − 0.826696 = 20.369621.

3.3 The large range

Finally, we bound the reciprocal sum over 2-pseudoprimes n > x_{0}. Let x > x_{0} and define y = exp(\sqrt{log x}), with y_{0} = y(x_{0}) = exp(10). For ease of notation, write p = P (n) and define t_{p} as the multiplicative order of 2 modulo p. Define the set Q = {p : t_{p} < p^{1/4}}, and let Q(x) = |{p ∈ Q : p ≤ x}|. Each 2-pseudoprime n > x_{0} falls into exactly one of the following categories:

1. p ≤ y,

2. p > y and p ∈ Q,

3. p > y and p ∉ Q.

For each 1 ≤ i ≤ 3, write 𝒜_{i} for the set of 2-pseudoprimes n ≤ x satisfying property i above and put A_{i}(x) = |{n ∈ 𝒜_{i} : n ≤ x}|.

Observe that A_{1}(x) = Ψ(x, y). By Lemma 10 we have

Ψ(x, y) ≤ 31.928253x/ exp(u/2)

where u = \frac{log x}{log y} = \frac{log x}{\sqrt{log x}} = \sqrt{log x}. We thus have

A_{1}(x) ≤ \frac{31.928253x}{exp (0.5\sqrt{log x})}

for x > x_{0}. Therefore, by partial summation,

∑_{n∈𝒜_{1}} ; n>x_{0} \frac{1}{n} ≤ ∫_{x_{0}}^{∞} \frac{31.928253 dt}{t exp (0.5\sqrt{log t})} = ∫_{100}^{∞} \frac{31.928253 dw}{exp(\sqrt{w/4})}

= 31.928253 [4e^{−\sqrt{w}/2}(\sqrt{w} + 2)]_{∞}^{100} < 10.326283.

Here we used substitution followed by integration by parts.

We now consider the second set, 𝒜_{2}. We first show that

Q(x) < 0.01588\sqrt{x}

for all x. A computer check shows that the claim holds for x ≤ e^{22}, that Q(e^{22}) = 26, and that

∏_{p∈Q} ; p≤e^{22} p > e^{496.34447}.

Assume that x > e^{22}. We have

∏_{p∈Q} ; p≤x p < ∏_{t<x^{1/4}} 2^{t} = exp (log 2 ∑_{t<x^{1/4}} t) ≤ exp (0.34799x^{1/2}) ,

while also

∏_{p∈Q} ; p≤x p = ∏_{p∈Q} ; p≤e^{22} p ∏_{p∈Q} ; e^{22}<p≤x p > e^{496.34447} (e^{22})^{Q(x)−26} = e^{22Q(x)−75.65553},

so that Q(x) < 0.01588x^{1/2} for all x as claimed. We thus have

A_{2}(x) < ∑_{2≤m<x/y} 0.01588 (\frac{x}{m})^{1/2} ≤ 0.01588x^{1/2} ∫_{1}^{x/y} \frac{dt}{t^{1/2}} < \frac{0.03176x}{y^{1/2}}.

By partial summation, we therefore have

∑_{n∈𝒜_{2}} ; n>x_{0} \frac{1}{n} ≤ ∫_{x_{0}}^{∞} \frac{0.03176 dt}{t exp(\sqrt{(log t)/4})} = ∫_{100}^{∞} \frac{0.03176 dw}{exp(\sqrt{w/4})} < 0.0102719.

Let n ∈ 𝒜_{3} and let p = P (n). Then t_{p} ≥ p^{1/4} > y^{1/4}. Following [11] we show that for such n we have n ≡ p (mod pt_{p}). We clearly have n ≡ p (mod p). We also have n ≡ p (mod t_{p}). To see this, note that n − p = (n − 1) − (p − 1). We have t_{p}|p − 1 by Fermat’s little theorem, and t_{p}|n−1 since n is a 2-pseudoprime and p|n. Since t_{p} < p we have gcd(p, t_{p}) = 1, and thus also n ≡ p (mod pt_{p}) as claimed. Thus the number of such n is bounded above by x/(pt_{p}) + 1. Also n > p (since p is not a pseudoprime), so the number of such n is in fact bounded above by x/(pt_{p}). Thus the number of 2-pseudoprimes in 𝒜_{3} satisfies

A_{3}(x) ≤ ∑_{p>y} \frac{x}{pt_{p}} ≤ x ∑_{p>y} \frac{1}{p^{5/4}} .

By Lemma 6 we have t/(log t) · (1 + 1/ log t) ≤ π(t) ≤ 1.1253816t/ log t for t ≥ y_{0}. Thus by partial summation we have

A_{3}(x) ≤ x (−\frac{π(y)}{y^{5/4}} + \frac{5}{4} ∫_{y}^{∞} \frac{π(t)}{t^{9/4}}dt)

≤ x (−\frac{1 + 1/ log y}{y^{1/4} log y} + \frac{5(1.1253816)}{4} ∫_{y}^{∞} \frac{dt}{(log t)t^{5/4}} )

= x (−\frac{1 + 1/ log y}{y^{1/4} log y} − \frac{5.626908}{4}Ei (−\frac{log y}{4} ))

= x (−\frac{1 + 1/\sqrt{log x}}{\sqrt{log x} · exp \sqrt{(log x)/16}} − 1.406727 · Ei (−\frac{\sqrt{log x}}{4})) ,

where

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

denotes the exponential integral function. By another application of partial summation, we thus have

∑_{n∈𝒜_{3}} ; n>x_{0} \frac{1}{n} ≤ − ∫_{x_{0}}^{∞} (\frac{1 + 1/\sqrt{log t}}{t\sqrt{log t} · exp(\sqrt{(log t)/16})} + \frac{1.406727 · Ei (−\frac{\sqrt{log t}}{4})}{t}) dt

= − ∫_{100}^{∞} \frac{(1 + 1/\sqrt{w}) dw}{\sqrt{w} · exp(\sqrt{w/16})} − 1.406727 ∫_{100}^{∞} Ei (−\frac{\sqrt{w}}{4}) dw

= −8e^{−2.5} + 2Ei(−2.5) + 1.406727 (100Ei(−2.5) + 56e^{−2.5})

< 2.2550278.

Here we substituted w = log t and used integration by parts. Adding the contributions from the small, middle and large ranges, we obtain

0.0152612 + 20.369621 + 12.5915827 < 32.9765,

completing the proof of Theorem 12.

4 The sum of reciprocals of the Carmichael numbers

Theorem 13. The sum of reciprocals of Carmichael numbers satisfies

0.004706 < ∑_{n∈𝒞} \frac{1}{n} < 27.8724.

To prove Theorem 13, we modify the small, middle and large ranges from the proof of Theorem 12 above.

4.1 The small range: n ≤ 10^{21}

A table of all 10000 Carmichael numbers up to 1713045574801 has been computed by R. Pinch, [15, 16]. Their contribution to the reciprocal sum is easily computed to be 0.004706 . . .. Pinch also determined that there are 20128200 additional Carmichael numbers up to 10^{21}. Therefore an upper bound for the sum of reciprocals of all Carmichael numbers n ≤ 10^{21} is given by

0.004707 + 20128200/1713045574803 < 0.0047188.

4.2 The middle range: 10^{21} < n ≤ x_{0} = exp(100)

We will use the following slight modification of Lemma 4, whose proof is nearly identical.

Lemma 14. Let a ∈ ℤ and d′ = 2 ∏_{i=2}^{10} p_{i}^{2}, where p_{i} denotes the i-th prime number. We have

∑_{n≡a(d′)} ; 10^{21}<n≤x_{0} \frac{1}{n} < \frac{51.6882395}{d′}.

Since Carmichael numbers are odd and squarefree by Lemma 1, they must lie in one of

E = ∏_{i=2}^{10}(p_{i}^{2} − 1)

residue classes modulo d′.

We may also remove the contribution to the sum from prime numbers. By Lemma 5 we have

∑_{10^{21}<p≤x_{0}} \frac{1}{p} > 0.7266133.

It follows from Lemma 1 that Carmichael numbers have at least three prime factors, so we may also remove the contribution to the sum from odd, squarefree numbers in the middle range with exactly two prime factors. Let π_{2}(x) = |{n = pq ≤ x : p < q}| denote the counting function of squarefree numbers with exactly two prime factors. Similarly, let π_{2}^{∗}(x) = |{n = pq ≤ x : 2 < p < q}| denote the counting function of odd squarefree numbers with exactly two prime factors. By a slight modification of Bayless and Klyve’s lower bound [6] on π_{2}(x), we are able to show that for all x ≥ 10^{21}, we have

π_{2}^{∗}(x) ≥ \frac{x(log log x − 0.300711)}{log x}.

Letting A^{∗} denote the set of odd squarefree numbers with exactly two prime factors, we therefore obtain by partial summation that

∑_{10^{21}<n≤x_{0}} ; n∈A^{∗} \frac{1}{n} ≥ \frac{log log x_{0} − 0.300711}{100} − \frac{log log 10^{21} − 0.300711}{log 10^{21}} + I,

where

I = ∫_{10^{21}}^{x_{0}} \frac{(log log t − 0.300711)dt}{t log t} = ∫_{log 10^{21}}^{100} \frac{(log w − 0.300711)dw}{w}

= [\frac{log^{2} w}{2} − 0.300711 log w]_{log 10^{21}}^{100} .

It follows that

∑_{10^{21}<n≤x_{0}} ; n∈A^{∗} \frac{1}{n} > 2.8327533.

Therefore, the contribution to the reciprocal sum from the middle range is bounded above by

51.6882395E/d′ − 0.7266133 − 2.8327533 < 17.5412697.

4.3 The large range: n > x_{0}

Finally, we bound the reciprocal sum over Carmichael numbers n > x_{0}. Let x > x_{0} and recall our definitions y = exp(\sqrt{log x}) and y_{0} = y(x_{0}) = exp(10). Write p = P (n). We split the Carmichael numbers n > x_{0} into two categories.

1. p ≤ y

2. p > y.

For i = 1, 2, write ℬ_{i} for the set of Carmichael numbers n ≤ x satisfying property i above and put B_{i}(x) = |{n ∈ ℬ_{i} : n ≤ x}|.

By the same argument in the proof of Theorem 12 above, we have

B_{1}(x) = Ψ(x, y) ≤ \frac{31.928253x}{exp (0.5\sqrt{log x})}

by Lemma 10, and

∑_{n∈ℬ_{1}} ; n>x_{0} \frac{1}{n} < 10.326283.

We next determine an upper bound for B_{2}(x). Observe that if p|n for a Carmichael number n, then n ≡ p (mod p(p − 1)). To see this, we clearly have p|n − p. Furthermore, since n − p = (n − 1) − (p − 1) and since p − 1|n − 1 by Lemma 1, we have p − 1|n − p. It follows that n ≡ p (mod p(p − 1)), since gcd(p, p − 1) = 1.

Therefore, the number of Carmichael numbers n ≤ x which are divisible by a given prime p is bounded above by x/(p(p − 1)). We therefore have

B_{2}(x) ≤ ∑_{p>y} \frac{x}{p(p − 1)} = x ∑_{p>y} \frac{1}{p(p − 1)}.

By partial summation, we have

∑_{p>y} \frac{1}{p(p − 1)} = −\frac{π(y)}{y(y − 1)} + ∫_{y}^{∞} \frac{π(t)(2t − 1) dt}{t^{2}(t − 1)^{2}}

≤ −\frac{π(y)}{y^{2}} + ∫_{y}^{∞} \frac{0.112539 · 2t dt}{t(t − 1)^{2}}

≤ −\frac{1}{y log y} (1 + \frac{1}{log y} ) + ∫_{y}^{∞} \frac{0.11255 · 2 dt}{t^{2}}

= \frac{0.2251}{y} − \frac{1}{y log y} (1 + \frac{1}{log y} ) .

Here we used Lemma 6 to bound

\frac{t}{log t} (1 + \frac{1}{log t}) ≤ π(t) ≤ 0.112539t

for all t ≥ y_{0}. Therefore, for all x ≥ x_{0} we have

B_{2}(x) ≤ \frac{x}{y} (0.2251 − \frac{1}{log y} (1 + \frac{1}{log y} )) .

It follows by another application of partial summation that

∑_{n∈ℬ_{2}} ; n>x_{0} \frac{1}{n} ≤ ∫_{x_{0}}^{∞} \frac{1}{t exp \sqrt{log t}} (0.2251 − \frac{1}{\sqrt{log t}} (1 + \frac{1}{\sqrt{log t}})) dt

= ∫_{100}^{∞} \frac{1}{exp \sqrt{w}} (0.2251 − \frac{1}{\sqrt{w}} (1 + \frac{1}{\sqrt{w}})) dw < 0.000126.

Adding the contributions from the small, middle and large ranges, we obtain 0.0047188+ 17.5412697 + 10.326409 < 27.8724, completing the proof of Theorem 13.

5 Concluding remarks

It will take more work to substantially sharpen the upper bound on the sum of reciprocals of 2-pseudoprimes. In fact, the result is close to optimal for the arguments used, in the following sense.

Reworking the arguments for different choices of the cutoff x = x_{0} for the large range, the coefficients appearing in the bounds for each case tend to vary relatively slowly. Therefore we may attempt to roughly optimize the bound by minimizing the function

f(x) = 0.0152612 + 0.37679(log x − log(10^{19} − d + 1)) − I + I_{1} + I_{2} + I_{3},

which represents the major contributions from the small, middle and large ranges to the reciprocal sum, where d is as defined in Lemma 4, and

I = log log x − log log 10^{19} − \frac{0.2}{log^{3} x} − \frac{0.2}{log^{3} 10^{19}} ,

I_{1} = ∫_{log x}^{∞} \frac{31.928253 dw}{exp(\sqrt{w/4})},

I_{2} = ∫_{log x}^{∞} \frac{0.03176 dw}{exp \sqrt{w/4}},

I_{3} = − ∫_{log x}^{∞} (\frac{1 + 1/\sqrt{w}}{\sqrt{w} · exp(\sqrt{w/16})} + 1.406727 · Ei (−\frac{\sqrt{w}}{4})) dw.

Applying the fundamental theorem of calculus and again substituting w = log x, the derivative is given by

f′(x) = \frac{1}{x} (0.37679 − J − J_{1} − J_{2} + J_{3}) ,

where

J = \frac{1}{w} + \frac{0.6}{w^{4}},

J_{1} = \frac{31.928253}{exp(\sqrt{w/4})},

J_{2} = \frac{0.03176}{exp(\sqrt{w/4})},

and

J_{3} = \frac{1 + 1/\sqrt{w}}{\sqrt{w} · exp(\sqrt{w/16})} + 1.406727 · Ei (−\frac{\sqrt{w}}{4}) .

Solving graphically for w, we find that the critical point is approximately w ≈ 79 so that x ≈ exp(79), and we have f(exp(79)) ≈ 32. This indicates that our cutoff of x_{0} = exp(100) for the large range is close to optimal for the method of argument used, especially keeping in mind that lowering the cutoff to x_{0} = exp(79) will in fact raise the constants appearing in the various upper bounds for the large range.

Furthermore, adjusting the coefficient in our definition of y = e^{\sqrt{c log x}} and reconsidering the argument, our choice of c = 1 used above gave better bounds than larger or smaller values of c that we also considered. However, it may be possible to further optimize the choice of coefficients, including those used in the proof of Lemma 10 bounding the count of smooth numbers.

Another possible way to improve this bound would be to find a way to effectively utilize more information about the 2-pseudoprimes. For instance, more specific residue classes in the middle range could be ruled out using an inclusion-exclusion argument.

Perhaps the bound on the sum of reciprocals of Carmichael numbers could be further optimized by utilizing more information about them, as well as optimizing the cutoff x_{0}. Another possibility for improving the bound for the sum of reciprocals of Carmichael numbers in the middle range is to use an inclusion-exclusion argument to remove not only the odd squarefree numbers with exactly two prime factors, but also the ones which fall in certain specific residue classes that can be ruled out.

Furthermore, Damgård et al [8, Thm. 5] proved that for all x ≥ 1, the number N(x) of Carmichael numbers up to x with exactly three prime factors satisfies the upper bound

N(x) ≤ 0.25\sqrt{x}(log x)^{11/4}.

Obtaining an explicit lower bound on the count of odd, squarefree numbers up to x having exactly three prime factors would therefore allow one to remove the contribution from all such numbers in the middle range and replace it using this tighter bound.

6 Acknowledgments

The authors would like to thank the referees for suggestions improving both the writing and the mathematics of this paper.

References

[1] W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers. Ann. of Math. 139 (1994), 703–722.

[2] T. Apostol, Introduction to Analytic Number Theory, Springer Science & Business Media, 2013.

[3] J. Bayless and P. Kinlaw, On consecutive coincidences of Euler’s function. Int. J. Number Theory 12 (2015), 1011–1026.

[4] J. Bayless and D. Klyve, On the sum of reciprocals of amicable numbers. Integers 11 (2011), 315–322.

[5] J. Bayless and D. Klyve, Reciprocal sums as a knowledge metric: theory, computation, and perfect numbers. Amer. Math. Monthly 120 (2013), 822–831.

[6] J. Bayless and D. Klyve, Sums over primitive sets with a fixed number of prime factors. Submitted.

[7] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Lecture Notes in Statistics, Vol. 182, Springer Science & Business Media, 2006.

[8] I. Damgård, P. Landrock, and C. Pomerance, Average case error estimates for the strong probable prime test. Math. Comp. 61 (1993), 177–194.

[9] J. M. De Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers, Graduate Studies in Mathematics, Vol. 134, Amer. Math. Soc., 2012.

[10] P. Dusart, Explicit estimates of some functions over primes. Ramanujan J. (2016), 1–25.

[11] P. Erdős, On pseudoprimes and Carmichael numbers. Publ. Math. Debrecen 4 (1956), 201–206.

[12] J. Feitsma, Pseudoprimes, 2013, http://www.janfeitsma.nl/math/psp2/index.

[13] G. Harman, Watt’s mean value theorem and Carmichael numbers. Int. J. Number Theory 4 (2008), 241–248.

[14] H. Nguyen, The reciprocal sum of the amicable numbers. Dartmouth College undergraduate honors thesis, Hanover, NH, 2014.

[15] R. Pinch, The Carmichael numbers up to 10^{21}, Proceedings of the Conference on Algorithmic Number Theory, Turku Centre for Computer Science 7 (2007), 129–131.

[16] R. Pinch, Tables relating to Carmichael numbers, 2005,

http://www.chalcedon.demon.co.uk/rgep/cartable.html.

[17] D. Platt and T. Trudgian, On the first sign change of θ(x) − x. Math. Comp. 85 (2016), 1539–1547.

[18] C. Pomerance, On the distribution of pseudoprimes. Math. Comp. 37 (1981), 587–593.

[19] J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers. Illinois J. Math. 6 (1962), 64–94.

[20] L. Schoenfeld, Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II, Math. Comp. 6 (1976), 243–269.

2010 Mathematics Subject Classification: Primary 11N25; Secondary 11Y99. Keywords: Carmichael number, pseudoprime, reciprocal sum, smooth number.

(Concerned with sequences \underline{A001567} and \underline{A002997}.)

Received April 7 2017; revised versions received May 31 2017; June 7 2017. Published in Journal of Integer Sequences, June 25 2017.

Return to Journal of Integer Sequences home page.