IMPROVED TECHNIQUES FOR LOWER BOUNDS FOR ODD PERFECT NUMBERS

R. P. Brent, G. L. Cohen and H. J. J. te Riele

Abstract. If N is an odd perfect number, and q^{k} ∥ N, q prime, k even, then it is almost immediate that N > q^{2k}. We prove here that, subject to certain conditions verifiable in polynomial time, in fact N > q^{5k/2}. Using this and related results, we are able to extend the computations in an earlier paper to show that N > 10^{300}.

1. Introduction. A natural number N is perfect if σ(N) = 2N, where σ is the positive divisor sum function. It is not known whether odd perfect numbers exist. In an earlier paper [2], the first two authors described an algorithm for demonstrating that there is no odd perfect number less than a given bound K, and applied it with K = 10^{160}.

That paper, and others referenced in it, are dependent on the simple observation that if N is an odd perfect number and q^{k} ∥ N, where q is prime and k is even, then N ≥ q^{k}σ(q^{k}) > q^{2k}. Methods based on this observation require the explicit factorisation of σ(q^{k}) for large values of q^{k}, which imposes a practical limit on their effectiveness. Fewer factorisations would be required if it were known that N > q^{l} for l > 2k. We shall prove below that, under certain conditions which are readily tested computationally and easily satisfied in the cases to be considered, we in fact have N > q^{5k/2} (Theorem 2, below). In some cases the exponent on q can be raised almost to 3k (Theorem 3).

The main result of this paper (Theorem 1) is still heavily dependent on the algorithm in [2], and we assume familiarity with that paper. It was stated at the end of that work that to continue the algorithm to obtain any substantial improvement of the earlier result required the factorisation of the 81-decimal-digit composite number σ(13^{72}); this factorisation has been completed and the result given in a postscript to [2]. But as our targeted lower bound increased, numerous other “unattainable” factorisations appeared to bar our way. One example is the factorisation of σ(3169^{36}), a composite number of 127 digits; since 3169^{5·36/2} = 3169^{90} > 10^{315}, this factorisation could be avoided by application of Theorem 2. This approach was still not sufficient in some instances, but more powerful results along the same lines allowed us to avoid these factorisations as well.

We have thus been able to prove

Theorem 1. There is no odd perfect number less than 10^{300}.

rpb116 typeset using AMS-TEX

1980 Mathematics Subject Classification. Primary 11A25; Secondary 11Y05, 11Y70.

Appeared in Mathematics of Computation 57 (1991), 857–868.

Copyright ◯^{c} 1991, American Mathematical Society.

To prove Theorem 1, there were nine cases, all detailed in Section 4, requiring special attention. Apart from these, the original algorithm of [2], with the “q^{2k} ” result, was sufficient.

A preliminary version of the present work is contained in [3]. There, the lower bound 10^{200} was obtained.

To describe the new method, we need the definition below. For each α ≥ 0, f_{α} is a function defined on the positive integers and satisfying 1 ≤ f_{α}(n) ≤ 2^{α} (so in particular f_{0}(n) = 1). We shall choose f_{α} as appropriate later.

Definition. Let q be an odd prime and k a positive integer. Define

E_{α}(q, k) = { p^{β} | p odd prime, β ≥ 2, β even or β ≡ p ≡ 1 (mod 4),
(∃j)(0 < j ≤ k, p^{β}/f_{α}(p) < q^{2j} and q^{j} ∥ σ(p^{β})) }

and

ϵ_{α}(q, k) = ∑_{p^{β}∈E_{α}(q,k)} log_{q}(q^{2j}f_{α}(p)/p^{β}).

(The value of j in the sum is that for which q^{j} ∥ σ(p^{β}).)

Write ϵ for ϵ_{0}.

We can compute an upper bound on ϵ_{α}(q, k) in time polynomial in q and k by an efficient “lifting” algorithm, described in Hardy and Wright [7, Theorem 123]. Usually, α = 0 and ϵ(q, k) is quite small; numerical results will be given in Section 3.

We assume in the following that N is an odd perfect number. According to Euler, we may write

N = q^{k} ∏_{i=1}^{j} p_{i}^{β_{i}},

where q and the p_{i} are distinct odd primes, p_{1} ≡ β_{1} ≡ 1 (mod 4) and k ≡ β_{2} ≡ ⋯ ≡ β_{j} ≡ 0 (mod 2). It is easy to show that j ≥ 2, and we make implicit use of this below; in fact, it is known that j ≥ 7 (Hagis [6]). Each p_{i}^{β_{i}}, and q^{k}, are called components of N.

Our new results follow.

Theorem 2. Let N, q^{k} and ϵ(q, k) be as above. Then, provided k ≥ 6ϵ(q, k) and σ(q^{k}) is not a square and has no prime factors less than \frac{1}{2}q^{ϵ(q,k)}, we have N > q^{5k/2}.

Theorem 3. Let N, q^{k}, ϵ(q, k) and p_{1} be as above. Let M be a unitary divisor of N (that is, M | N and gcd(M, N/M) = 1), such that q ∤ M, q ∤ σ(M) and p_{1} ∤ M. Then

N > \frac{1}{2}Mq^{3k−k_{1}−ϵ(q,k)},

where q^{k_{1}} ∥ p_{1} + 1.

2. Proofs of Theorems 2 and 3. The proofs depend on a number of lemmas, some of which will also be used independently in the proof of Theorem 1.

Lemma 1. If p and q are odd primes with p | σ(q^{k}) and q^{m} | p + 1, then k ≥ 3m.

Proof. Since q^{m} | p + 1, we have p + 1 = 2aq^{m} for some a > 0. Then, since p | σ(q^{k}) = (q^{k+1} − 1)/(q − 1),

q^{k+1} − 1 = (2aq^{m} − 1)R,

where R > 0, and this implies k ≥ m. From the preceding equation, we have R ≡ 1 (mod q^{m}), so R = bq^{m} + 1 say, and clearly b > 0.

Thus

q^{k+1} − 1 = (2aq^{m} − 1)(bq^{m} + 1),  (1)

so q^{k+1} > aq^{m} · bq^{m} ≥ q^{2m}, from which k ≥ 2m.

We also have

q^{k+1−m} = 2abq^{m} + 2a − b,

so b = 2a + λq^{m}, where λ = 2ab − q^{k+1−2m}, the latter implying λ ≠ 0. Then we cannot have both b < q^{m} and 2a < q^{m}, since in that case

|λ| = \frac{|b − 2a|}{q^{m}} < 1,

a contradiction. Hence, b ≥ q^{m} or 2a > q^{m}.

From (1), if 2a > q^{m}, then

q^{k+1} − 1 > (q^{2m} − 1)(q^{m} + 1),

so q^{k+1} > q^{3m} + q^{2m} − q^{m} ≥ q^{3m}; and if b ≥ q^{m}, then

q^{k+1} − 1 ≥ (2q^{m} − 1)(q^{2m} + 1),

so q^{k+1} ≥ 2q^{3m} + 2q^{m} − q^{2m} > q^{3m}. Either way, we infer that k ≥ 3m, as required.

The example p = 5, q = 3, k = 3, m = 1 shows this result to be best possible.

Lemma 2. Let q be an odd prime and let S be any nonempty set of prime powers p^{β}, with p odd and β at least 2 and either even or satisfying β ≡ p ≡ 1 (mod 4). For each p_{i}^{β_{i}} ∈ S, suppose q^{k_{i}} ∥ σ(p_{i}^{β_{i}}) and k ≥ ∑ k_{i}. Then

log_{q} ∏_{p_{i}^{β_{i}} ∈S} \frac{σ(p_{i}^{β_{i}})}{f_{α}(p_{i})} > 2 ∑ k_{i} − ϵ_{α}(q, k).

Proof. We have quite generally that

\frac{σ(p_{i}^{β_{i}})}{f_{α}(p_{i})} > \frac{p_{i}^{β_{i}}}{f_{α}(p_{i})} = q^{2k_{i}−(2k_{i}−log_{q}(p_{i}^{β_{i}} /f_{α}(p_{i})))} = q^{2k_{i}−log_{q}(q^{2k_{i}} f_{α}(p_{i})/p_{i}^{β_{i}})},

while if p_{i}^{β_{i}} ∈ S\E_{α}(q, k), then p_{i}^{β_{i}}/f_{α}(p_{i}) ≥ q^{2k_{i}}. Thus, where E_{α} = E_{α}(q, k),

log_{q} ∏_{p_{i}^{β_{i}} ∈S} \frac{σ(p_{i}^{β_{i}})}{f_{α}(p_{i})} > 2 ∑ k_{i} − ∑_{p_{i}^{β_{i}} ∈S∩E_{α}} log_{q}(q^{2k_{i}}f_{α}(p_{i})/p_{i}^{β_{i}})

≥ 2 ∑ k_{i} − ∑_{p_{i}^{β_{i}} ∈E_{α}} log_{q}(q^{2k_{i}}f_{α}(p_{i})/p_{i}^{β_{i}})

≥ 2 ∑ k_{i} − ϵ_{α}(q, k),

as required.

We remark that Lemmas 1 and 2 require no reference to odd perfect numbers. Lemma 3. Let N, q^{k} and p_{1}^{β_{1}} be as in Section 1.

(i) If β_{1} > 1 then

N > \frac{1}{2}q^{3k−ϵ_{α}(q,k)} ∏_{i=1}^{j} f_{α}(p_{i}).

(ii) If β_{1} = 1 then

N > q^{3k−k_{1}−ϵ_{α}(q,k)} ∏_{i=2}^{j} f_{α}(p_{i}),

where q^{k_{1}} ∥ p_{1} + 1.

Proof. (i) Apply Lemma 2 with S equal to the set of components of N/q^{k}. Then, in Lemma 2, ∑ k_{i} = k and

2N = σ(N) = σ(q^{k}) ∏_{i=1}^{j} \frac{σ(p_{i}^{β_{i}})}{f_{α}(p_{i})} ∏_{i=1}^{j} f_{α}(p_{i})

> q^{k} · q^{2k−ϵ_{α}(q,k)} · ∏_{i=1}^{j} f_{α}(p_{i}).

(ii) We again apply Lemma 2, this time with S equal to the set of components of N/q^{k}p_{1}. Then ∑ k_{i} = k − k_{1} and

2N = σ(N) = σ(q^{k})σ(p_{1}) ∏_{i=2}^{j} \frac{σ(p_{i}^{β_{i}})}{f_{α}(p_{i})} ∏_{i=2}^{j} f_{α}(p_{i})

> q^{k} · (p_{1} + 1) · q^{2(k−k_{1})−ϵ_{α}(q,k)} · ∏_{i=2}^{j} f_{α}(p_{i}).

Since p_{1} + 1 ≥ 2q^{k_{1}}, the result follows.

Corollary 1. Let N, q^{k} and p_{1}^{β_{1}} be as above. If either (i) β_{1} > 1, or (ii) β_{1} = 1 and p_{1} | σ(q^{k}), then

N > q^{8k/3−ϵ(q,k)}.

Proof. Take α = 0 in Lemma 3. (i) Since k ≥ 2 and q ≥ 3, we have q^{k/3} > 2 and the result follows from Lemma 3 (i). (ii) From Lemma 1, k ≥ 3k_{1} so the result follows from Lemma 3 (ii) since 3k − k_{1} ≥ 3k − k/3 = 8k/3.

Lemma 4. Let N, q^{k} and p_{1} be as in Section 1. Suppose that σ(q^{k}) is not a perfect square and is not divisible by p_{1} or any prime number less than B. Then

N^{2} > 2Bq^{5k−ϵ_{α}(q,k)} ∏_{i=2}^{j} f_{α}(p_{i}).

Proof. We shall prove this lemma in the case where q | p_{1} + 1 and p_{1} ∥ N. (Minor adjustments are needed for the other cases.) Suppose q^{k_{1}} ∥ p_{1} + 1. Since σ(q^{k}) is not a perfect square, there is a prime, p_{2} say, but not p_{1}, which divides σ(q^{k}) to an odd power and so divides N to a higher (even) power. Also p_{1}+1 ≥ 2q^{k_{1}} and p_{2} ≥ B, so

N ≥ q^{k}σ(q^{k})p_{1}p_{2}
≥ q^{k} · q^{k}(1 + q^{−1}) · 2q^{k_{1}}(1 − \frac{1}{2}q^{−k_{1}}) · B
> 2Bq^{2k+k_{1}}.

From Lemma 3 (ii), we also have N > q^{3k−k_{1}−ϵ_{α}(q,k)} ∏_{i=2}^{j} f_{α}(p_{i}). Hence

N^{2} > 2Bq^{5k−ϵ_{α}(q,k)} ∏_{i=2}^{j} f_{α}(p_{i}),

as required.

Proof of Theorem 2. Take α = 0. Since k ≥ 6ϵ(q, k), we have 8k/3 − ϵ(q, k) ≥ 5k/2, and the theorem follows from Corollary 1, unless β_{1} = 1 and σ(q^{k}) is not divisible by p_{1}. But then the result follows from Lemma 4, with B ≥ \frac{1}{2}q^{ϵ(q,k)}.

Proof of Theorem 3. As in the proof of Lemma 3, we consider two cases. If β_{1} > 1 then apply Lemma 2 with S equal to the set of components of N/Mq^{k}. Then ∑ k_{i} = k, since q ∤ σ(M), and

2N = σ(N) = σ(M)σ(\frac{N}{M} ) = σ(M)σ(q^{k}) ∏_{\begin{matrix}i=1 \\ p_{i}∤M \end{matrix}}^{j} σ(p_{i}^{β_{i}})

> M · q^{k} · q^{2k−ϵ(q,k)} = Mq^{3k−ϵ(q,k)}.

If β_{1} = 1, then apply Lemma 2 with S equal to the set of components of N/Mq^{k}p_{1}. Then ∑ k_{i} = k − k_{1} and

2N = σ(M)σ(q^{k})σ(p_{1}) ∏_{\begin{matrix}i=2 \\ p_{i}∤M \end{matrix}}^{j} σ(p_{i}^{β_{i}})

> M · q^{k} · 2q^{k_{1}} · q^{2(k−k_{1})−ϵ(q,k)} = 2Mq^{3k−k_{1}−ϵ(q,k)}.

The result follows.

3. Computation of ϵ_{α}(q, k). Theorem 2 is useful because an upper bound on ϵ_{α}(q, k) can be computed in time which is bounded by a low degree polynomial in q and k. We first outline an algorithm for this computation, and then give a numerical example.

Suppose p^{β} ∈ E_{α}(q, k), where E_{α}(q, k) is defined in Section 1. Since p ≥ 3 and p^{β} < 2^{α}q^{2k}, we have β < α + 2k log_{3} q. Thus, to establish the polynomial-time result, it is sufficient to suppose that β is fixed.

Define F (x) = 1+x+x^{2}+⋯+x^{β}. We can enumerate the set S_{j} of least positive residues modulo q^{j} of F (x) ≡ 0 (mod q^{j}) by the “lifting” algorithm described in [7, §8.3]. If j = 1, we can simply check all possible solutions 1, 2, …, q − 1 (although faster methods, using a primitive root (mod q), are preferable if q is large). If j > 1, we apply Theorem 123 of [7] to obtain S_{j} from S_{j−1}, using what is essentially an application of Newton’s method. Since F (x) is a polynomial of degree β, the number |S_{j}| of solutions is bounded by β.

Define T_{j} = { s + λq^{j} | s ∈ S_{j}, λ ≥ 0, (s + λq^{j})^{β} < f_{α}(s + λq^{j})q^{2j} }. Clearly, |T_{j}| ≤ ⌈2^{α/β}⌉ |S_{j}|. Since p^{β} ∈ E_{α}(q, k), there is some j, 0 < j ≤ k, such that q^{j} ∥ σ(p^{β}) and p^{β} < f_{α}(p)q^{2j}. Thus, to enumerate such p^{β}, we need only check the elements of T_{1}, T_{2}, …, T_{k} for primality. In order to obtain an upper bound on ϵ_{α}(q, k), it is sufficient to use a polynomial-time probabilistic primality test, for the inclusion of a composite p will only increase the computed sum ∑ log_{q}(q^{2j}f_{α}(p)/p^{β}). In practice, below, the upper bounds on each ϵ_{α}(q, k) are in fact exact results, rounded up if not zero, since each p used was shown to be prime.

Example. To illustrate the algorithm, consider the computation of ϵ(3169, 36). If β = 2, F (x) = 1 + x + x^{2}, so S_{1} = {97, 3071} is the set of solutions of F (x) ≡ 0 (mod 3169). We construct the sets S_{2}, S_{3}, …, S_{36} as in [7, §8.3], and in each case |S_{j}| = 2. (In this example α = 0 so T_{j} = S_{j}; in general we would add a small number of multiples of q^{j} to the elements of S_{j} in order to obtain the set T_{j}.) Applying a probabilistic primality test to the elements of T_{1}, T_{2}, …, T_{36} rules out all but three possible odd prime p such that 3169^{j} ∥ σ(p^{2}):

j = 1, p = 97;
j = 3, p = 5875516237; and
j = 11, p = 266602399893630549086712579594816998201.

The contributions log_{3169}(3169^{2j}/p^{2}) from these three pairs (j, p) are respectively bounded above by 0.8651, 0.4192, and 0.0482.

For β ≥ 4, we proceed similarly, but we find no solutions satisfying all the constraints. (This is typical, since it is unlikely that the constraint p^{β} < f_{α}(p)q^{2j} will be satisfied if β ≥ 4.) We conclude that only the three pairs given above can contribute to ϵ(3169, 36), so ϵ(3169, 36) ≤ 1.3325.

Table 1 gives the details of all nonzero contributions to ϵ_{α}(q, k) in the cases relevant to the proof of Theorem 1. Note that there is only one case with β > 2.

Table 1. Nonzero contributions to ϵ_{α}(q, k), q^{j} ∥ σ(p^{β})
α  q  k  j β log_{q}(q^{2j}f_{α}(p)/p^{β}) p (see below)
0  7 172  8 2  0.5496 …  3376853
19 2  0.0607 …  10744682090246617
25 2  0.3689 …  936579478224094047977
61 2  1.7036 …  6778 …
119 2  1.0771 …  1292 …
150 2  0.3796 …  4020 …
0  3221 42  1 4  0.8125 …  11
0 612067 22  1 2  0.3398 …  63601
17 2  0.2253 …  5291 …
0  3169 36  1 2  0.8650 …  97
3 2  0.4191 …  5875516237
11 2  0.0481 …  2666 …
221  3 240  1 2  0.9380 …  37

Large primes p occurring above

677822686658425215407071060694728215733634249273881 1292705670586158487568763039916765694399830534390031 9630427909162956962804028786608263511417448696587

40205637668275700485119982296550937753326347643003642516228059494 71752457774955475739650336310509313359098137765181615640612833

52915283185303600217046163660913353511950087333134 106429889256916343584191707324489815681786937851

266602399893630549086712579594816998201

4. Proof of Theorem 1. Except for the nine cases to be discussed below, the proof is a straight-forward extension of the algorithmic method given in [2]. In particular, it is still valid that the theorem will follow once the primes 127, 19, 7, 11, 31, 13, 3 and 5 are eliminated as possible divisors of N. (As in [2], the elimination of these primes was carried out in the order given.)

The computer output towards the proof of Theorem 1 has 12655 lines. Some relevant extracts are shown below. In these, D means the indicated divisor has already been considered; for details, see [2]. The cases requiring special attention are the following.

(i) Line 7343 concerns the possibility that 3221^{42} ∥ N. Note that σ(3221^{42}) = c_{148}, a composite number with 148 decimal digits, unable to be factorised at this time. We have ϵ(3221, 42) = log_{3221}(3221^{2}/11^{4}) ≤ 0.8126 (see Table 1); the conditions of Theorem 2 are satisfied, so

N > 3221^{105} > 10^{368}.

(Such discussions will subsequently be much abbreviated.)

(ii) Line 7163, σ(7^{172}) = c_{146}, ϵ(7, 172) ≤ 4.1400. By Theorem 2,

N > 7^{430} > 10^{363}.

(iii) Line 7985, σ(612067^{22}) = c_{128}, ϵ(612067, 22) ≤ 0.5652. By Theorem 2,

N > 612067^{55} > 10^{318}.

(iv) Line 8866, σ(3169^{36}) = c_{127}, ϵ(3169, 36) ≤ 1.3324. By Theorem 2,

N > 3169^{90} > 10^{315}.

(v) Line 4479, σ(467^{46}) = c_{123}. We apply Lemma 3, with α = 0. The antecedents of this case (see Figure 1) show that p_{1} = 2801 and k_{1} = 1. Since ϵ(467, 46) = 0,

N > 467^{137} > 10^{365}.

Figure 1. σ(467^{46})

4340:  7^{2} ⇒ 19 …, D
4341:  7^{4} ⇒ 2801
4342:  2801^{1} ⇒ 3 · 467
4343:  467^{2} ⇒ 19 …, D

(some lines omitted)

4479:  467^{46} ⇒ c_{123}, case (v)

(vi) Line 9527, σ(191^{46}) = c_{105}. See Figure 2. Lemma 3, with α = 0, p_{1} = 30941, k_{1} = 1 and ϵ(191, 46) = 0, gives

N > 191^{137} > 10^{312}.

(vii) Line 11343, σ(36389^{22}) = c_{101}. Observing the antecedents of this case (Figure 3), we may apply Theorem 3 with M = 3^{β_{2}} ≥ 3^{18}, p_{1} = 363889, k_{1} = 1 and ϵ(36389, 22) = 0. (Since 3 is a primitive root (mod 36389) and β_{2} is even, we know that 36389 ∤ σ(3^{β_{2}}).) Then

N > \frac{1}{2} · 3^{18}36389^{65} > 10^{304}.

Figure 2. σ(191^{42}) and σ(191^{46})

8653:  13^{1} ⇒ 7, D
8654:  13^{2} ⇒ 3 · 61

(some lines omitted)

9473:  13^{4} ⇒ 30941
9474:  30941^{1} ⇒ 3^{4} · 191
9475:  191^{2} ⇒ 7 …, D

(some lines omitted)

9526:  191^{42} ⇒ c_{96}, case (viii)
9527:  191^{46} ⇒ c_{105}, case (vi)

(viii) Line 9526, σ(191^{42}) = c_{96}. The antecedents of this case (Figure 2) show that p_{1} = 30941 and 191 ∥ σ(p_{1}). Then, in Lemma 3, k_{1} = 1 and f_{α}(p_{1}) ≥ 1, so that

N > q^{3k−1−ϵ_{α}(q,k)} ∏_{i=2}^{j} f_{α}(p_{i}),

with q = 191, k = 42. The bound obtainable from Lemma 3 with α = 0 is not quite good enough, so (for the first time) we need to take α > 0. For any prime p, we set

f_{α}(p) = \{ \begin{matrix}(\frac{p}{p − 1})^{α} & if p | N, p ≠ 191 or 30941, \\ 1 & otherwise. \end{matrix}

Since

2 = \frac{σ(N)}{N} < ∏_{p|N} \frac{p}{p − 1} = \frac{191}{190} \frac{30941}{30940} ∏_{i=2}^{j} \frac{p_{i}}{p_{i} − 1},

we have

∏_{i=2}^{j} f_{α}(p_{i}) > (2 · \frac{190}{191} · \frac{30940}{30941})^{α} .

We need to take α large enough that ∏_{i=2}^{j} f_{α}(p_{i}) is large but not so large that ϵ_{α}(191, 42) > 0. After some experimentation, we find that with α = 50 we have ϵ_{50}(191, 42) = 0 and

N > 191^{125} (2 · \frac{190}{191} · \frac{30940}{30941})^{50} > 10^{300}.

Figure 3. σ(36389^{22})

10615: 3^{2} ⇒ 13, D

(some lines omitted)

11214: 3^{18} ⇒ 1597 · 363889
11215:  363889^{1} ⇒ 5 · 36389
11216:  36389^{2} ⇒ 1429 · 926659

(some lines omitted)

11343:  36389^{22} ⇒ c_{101}, case (vii)

(ix) Line 12201, σ(3^{240}) = c_{115}. Since ϵ(3, 240) = 0 and

3^{8·240/3} = 3^{640} > 10^{305},

by Corollary 1 we may assume that β_{1} = 1 and p_{1} ∤ σ(3^{240}). Then, from Lemma 3 (ii),

N > 3^{720−k_{1}} > 10^{300}

if k_{1} ≤ 91. Thus we may assume further that k_{1} ≥ 92, so that p_{1} > 3^{92}. For any prime p, we set

f_{α}(p) = \{ \begin{matrix}(\frac{p}{p − 1})^{α} & if p | N, p ≠ 3 or p_{1}, \\ 1 & otherwise. \end{matrix}

Then, as in (viii),

∏_{i=2}^{j} f_{α}(p_{i}) > (2 · \frac{2}{3} · \frac{p_{1} − 1}{p_{1}})^{α} .

We find that with α = 221 we have ϵ_{221}(3, 240) ≤ 0.9381. (It is relevant for this calculation that 7, 13, 19, 31 are “forbidden” divisors. Otherwise, there would be contributions from these primes to the sum defining ϵ_{221}(3, 240).) Using Lemma 4 with B = 1, we have

N^{2} > 2 · 3^{1200−0.9381} (2 · \frac{2}{3} · \frac{3^{92} − 1}{3^{92}})^{221} > 10^{600}.

This completes the proof of Theorem 1.

The entire computer output is printed in [4]. A copy has been deposited in the UMT file of this journal.

We should mention that the size of the task precluded us from being as fastidious as we were in [2]. The proof contains 199 partial factorisations. We estimate that at most 1658 lines would have been saved if those factorisations were completed. In most cases, the extra lines result from expanding the proof tree using a smaller prime than would be available if the complete factorisation at the relevant line were known. In ten cases, the program had to backtrack from an assumed prime divisor q to another in the same or an earlier branch in order to avoid a composite σ(q^{k}) for which we could find no useful factors. The nine special cases (i)–(ix) arose because this option was not available or was impractical. (This can be seen in Figures 1 and 2.) On the other hand, there were three cases where the proof was shortened by branching on a prime smaller than the largest available (but there was no systematic search for such possibilities).

The program for the proof of Theorem 1 differs from that used in [2] in that, besides calculating bounds named B1, B2 and B3 there, it also calculates, when necessary, “bounds” named B25 and B30, which are ⌊log_{10} q^{5k/2}⌋ and ⌊log_{10} q^{3k}⌋, respectively, for the current assumed component q^{k}. However, the B25 and B30 “bounds” need not exceed 10^{300}, and the program does not incorporate the calculation of values of ϵ_{α}, so that they are not rigorous and are used only to flag the need for special discussions, such as those above.

A supplement published with [2] contained the output for that proof. In [4], we include a list of factors of p^{n} − 1 for p prime, 13 ≤ p < 10000, and those values of n (all prime) which arose in our work. This complements the lists in [5] and should prove similarly useful. We take this opportunity to announce the availability of a machine-readable database of factors [1], including all those necessary for the proof of Theorem 1.

Acknowledgments. Some of the factorisations required for the proof of Theorem 1 were obtained using the Fujitsu VP-100 of the Australian National University Supercomputer Facility. Some others were obtained from [5]. We thank the referee for his assistance in improving the exposition.

Computer Sciences Laboratory Research School of Physical Sciences The Australian National University GPO Box 4 Canberra, ACT 2601, Australia

School of Mathematical Sciences University of Technology, Sydney PO Box 123 Broadway, NSW 2007, Australia

Centrum voor Wiskunde en Informatica Kruislaan 413 1098 SJ Amsterdam, The Netherlands

1. R. P. Brent, “Factor: an integer factorization program for the IBM PC”, Report TR-CS-89-23, Computer Sciences Laboratory, Australian National University, October 1989.

2. R. P. Brent and G. L. Cohen, “A new lower bound for odd perfect numbers”, Math. Comp., v. 53, 1989, pp. 431–437, S7–S24.

3. R. P. Brent, G. L. Cohen and H. J. J. te Riele, “An improved technique for lower bounds for odd perfect numbers”, Report TR-CS-88-08, Computer Sciences Laboratory, Australian National University, August 1988.

4. R. P. Brent, G. L. Cohen and H. J. J. te Riele, “Improved techniques for lower bounds for odd perfect numbers”, Report CMA-R50-89, Centre for Mathematical Analysis, Australian National University, August 1988.

5. J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of b^{n} ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to High Powers, American Mathematical Society, Providence, Rhode Island, Second Edition, 1988.

6. P. Hagis, Jr., “Outline of a proof that every odd perfect number has at least eight prime factors”, Math. Comp., v. 34, 1980, pp. 1027–1032.

7. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fourth Edition, Oxford University Press, 1962.