A Fibonacci-like sequence of composite numbers

John W. Nicol University of Illinois, Urbana, IL

                   nicol@alumni.cs.cmu.edu

Submitted: June 17, 1998; Submitted in revised form: October 12, 1999; Accepted: November 6, 1999.

Abstract

In 1964, Ronald Graham proved that there exist relatively prime natural numbers a and b such that the sequence {A_{n}} defined by

A_{n} = A_{n−1} + A_{n−2} (n ≥ 2; A_{0} = a, A_{1} = b)

contains no prime numbers, and constructed a 34-digit pair satisfying this condition.

In 1990, Donald Knuth found a 17-digit pair satisfying the same conditions. That same year, noting an improvement to Knuth’s computation, Herbert Wilf found a yet smaller 17-digit pair.

Here we improve Graham’s construction and generalize Wilf’s note, and show that the 12-digit pair

(a, b) = (407389224418, 76343678551)

also defines such a sequence.

Mathematical Reviews Subject Numbers: 11B39, 11N99.

1 Introduction

Ronald Graham [2] proved that there exist relatively prime natural numbers a and b such that the sequence {A_{n}} defined by

A_{n} = A_{n−1} + A_{n−2} (n ≥ 2; A_{0} = a, A_{1} = b)

contains no prime numbers. Graham’s pair (a, b) was

(331635635998274737472200656430763, 1510028911088401971189590305498785).

Donald Knuth [4] found the smaller pair

(a, b) = (62638280004239857, 49463435743205655).

Herbert Wilf [8] noted that Knuth’s computation could be improved and so found the pair

(a, b) = (20615674205555510, 3794765361567513).

Here we show that Wilf actually generalized the system of congruences given by Graham. By further generalizing the system, improving Graham’s construction, and applying Knuth’s method to the cases that are generated, we show that the pair

(a, b) = (407389224418, 76343678551)

also defines such a sequence.

Graham constructed the following 18 triples of numbers (p_{k}, m_{k}, r_{k}) such that

1. p_{k} is prime

2. p_{k} | F_{n} ⟺ n | m_{k} (F_{n} is the Fibonacci number.)

3. The congruences x ≡ r_{k} (mod m_{k}) cover the integers (i.e., for every number n, there exists a k, 1 ≤ k ≤ 18 such that n ≡ r_{k} (mod m_{k}))

\begin{matrix}(3, 4, 1) & (2, 3, 2) & (5, 5, 1) \\ (7, 8, 3) & (17, 9, 4) & (11, 10, 2) \\ (47, 16, 7) & (19, 18, 10) & (61, 15, 3) \\ (2207, 32, 15) & (53, 27, 16) & (31, 30, 24) \\ (1087, 64, 31) & (109, 27, 7) & (41, 20, 10) \\ (4481, 64, 63) & (5779, 54, 52) & (2521, 60, 0) \end{matrix}

Note that the first column covers all n ≡ 1 (mod 2), the second column covers all n ≡ 2 (mod 3) and n ≡ 4 (mod 6), and the third column covers all n ≡ 0 (mod 6), which clearly covers all n.

Graham then constructed a and b such that

4. p_{k} | A_{n} ⟺ n ≡ r_{k} (mod m_{k}) thereby assuring that for all n, A_{n} was composite. Knuth then minimized the a and b satisfying the last condition. Wilf, armed with the observation that if a < b, then the pair (b − a, a) forms a smaller sequence, took one of the “non-minimal” pairs found by Knuth and projected it backwards.

Does this mean Knuth had not found the minimal solution? Actually, he had, but he found the minimal solution given the triples (p_{k}, m_{k}, r_{k}). Wilf’s note amounts to the observation that adding the number i to every r_{k} creates another covering of the integers. Wilf found the minimal pair given the triples (p_{k}, m_{k}, (r_{k} + 4)), by projecting backwards four steps.

In this paper, we generate all possible choices for the r_{k} (thus finding all possible coverings of the integers given the m_{k}) and minimize the a’s and b’s constructed by Knuth’s method. Thus the minimum values of a and b are determined for the pairs (p_{k}, m_{k}).

2 Proof of Regularity

Before minimizing the r_{k}, we wish to strengthen condition (3) to be

(3′). The congruences x ≡ r_{k} (mod m_{k}) are a regular covering (also called an irredundant covering) [7, 3] of the integers.

(A regular covering is a covering of the integers that has no unnecessary congruence relations. Thus a covering {(m_{k}, r_{k})} is regular if there does not exist an i such that {(m_{k}, r_{k}) : k ≠ i} covers the integers.)

For if this is not the case, then we are forcing a and b to satisfy an extra triple, and thus are perhaps not finding minimum values for a and b.

Now let us verify that the above pairs (m_{k}, r_{k}) form a regular covering. Assume not (i.e., assume at least one pair (m_{l}, r_{l}) is not required and can be removed). Take d, e, f all of the same parity and in different residue classes modulo 3, and c of the opposite parity. Let us first assume that a pair (m_{l}, r_{l}) can be removed from the first column. Then, by inspection, for some c_{1} and c_{2} where c_{1} and c_{2} are of opposite parity, the first column does not cover the integers n ≡ c_{1} and c_{2} (mod 64).

Thus, the second and third columns must cover these. But note that the other even m_{k} (18,54,10,20,30,60) can only contribute to covering either the integers n ≡ c_{1} or n ≡ c_{2} (mod 64), since c_{1} and c_{2} have opposite parity. Thus, at most three of the even m_{k} contribute to covering one of these, let us say c_{1}.

Note that for the m_{k} above to be able to cover the integers n ≡ c_{1} (mod 64), then they divided by their greatest common divisor with 64 must cover all of the integers.

Thus, the moduli (3,9,27,27,5,15) and at most three of (9,27,5,5,15,15) should suffice to cover the integers, which by inspection is clearly not the case.

So no pairs can be removed from the first column. Note also that the first column is an exact covering of the integers n ≡ c (mod 2) (i.e., if n ≢ c (mod 2), then n is not covered by the first column).

Let us now assume that a pair (m_{l}, r_{l}) can be removed from the second column. This means the second columns does not cover the integers n ≡ d and e (mod 6).

Then, by inspection, the first and second columns do not cover the integers n ≡ d_{1} (mod 18) and n ≡ d_{2} (mod 54), where d_{1} ≢ d_{2} (mod 3), but d_{1} ≡ d_{2} ≢ c (mod 2).

Again, this implies that the m_{k} not divisible by 3 plus at most one of the m_{k} divisible by 3 in the third column will cover the integers n ≡ d_{2} (mod 54). Thus one of the moduli (5,10,20) and one of the moduli (15,30,60) will cover the integers n ≡ d_{2} (mod 54), which is clearly false.

So the second column must cover the integers n ≡ d and e (mod 6), which means the third column must cover the integers n ≡ f (mod 6). After dividing the m_{k} of the third column by their greatest common divisor with 6, it is clear that none of the moduli of the third column can be removed.

Thus the covering system (m_{k}, r_{k}) is regular, and is in fact regular for all valid choices of the r_{k}.

3 A Slight Improvement to Graham’s Construction

Although the given covering system is regular, this does not imply that it is the optimal covering system (even after optimizing over the r_{k}).

Although it is not clear how to prove that one system is better than another (without computing the minimal solution for each system), a good heuristic seems to be choosing small p_{k}, and using as few congruences as possible.

Note that if the second and third columns covers n ≡ 0, 2, 4, 5 (mod 6), as done in Graham’s construction, then the first column need only cover n ≡ 1, 3 (mod 6). The first column of Graham’s construction covers n ≡ 1 (mod 2), which is perhaps overkill.

If we replace the triples (2207, 32, 15), (1087, 64, 31), and (4481, 64, 63) with the triples (23, 24, 15) and (1103, 48, 31), we obtain a covering with smaller p_{k} and one fewer congruence.

Since we have proven that Graham’s system is regular, showing that this new system is regular is rather simple. We need only show that no subset of the first column covers n ≡ 1, 3 (mod 6).

It suffices to show that the modulus 48 cannot be removed. We assume otherwise; but by inspection, the moduli (4, 8, 16, 24) cannot cover n ≡ 1, 3 (mod 6).

Thus the new system is also regular, and the minimal solution for this system is roughly five hundred times smaller than the minimal solution for Graham’s system.

4 Counting the cases

Now, we determine the number of possible distinct coverings given the m_{k} above.

The first column must cover the congruences n ≡ g (mod 6) and n ≡ h (mod 6), where g and h are of the same parity and g ≢ h (mod 3). There are twelve ways this can be done (order is important, since the p_{k} are distinct). There are then two choices for the modulus 4, two for the modulus 8, and two for the modulus 16. Thus, there are 12 × 2^{3} = 96 ways to choose the first column.

We fix the first column (and thus g and h), and note that all the even m_{k} in the second and third column must have r_{k} ≢ g (mod 2). The choice of residue for the modulus 3 is forced. There are then six choices for the modulus 9, two for 18, three for 27, and two for the second 27. Thus, there are 6 × 2 × 3 × 2 = 72 ways that the second column can be chosen.

Finally, fixing the first and second column, and that the m_{k} divisible by 4 in the third column must not have their r_{k} be congruent modulo 4, we see that there are precisely five choices for the modulus 5, four for the modulus 10, three for 15, two for 30, and two for 20. So there are 5 × 4 × 3 × 2 × 2 = 240 ways that the third column can be chosen.

5 The Result

Now, applying Knuth’s method [4] to each of the 96 × 72 × 240 = 1658880 cases above, we find the smallest values of a and b to be:

(a, b) = (407389224418, 76343678551)

with the triples below:

(3, 4, 3)  (2, 3, 0)  (5, 5, 3)
(7, 8, 1)  (17, 9, 5)  (11, 10, 0)
(47, 16, 5)  (19, 18, 8)  (61, 15, 7)
(23, 24, 5)  (53, 27, 11) (31, 30, 16)
(1103, 48, 13) (109, 27, 2) (41, 20, 14)
(5779, 54, 20) (2521, 60, 4)

It is trivial to verify that the sequence A_{n} defined by a and b above will consist of only composite terms.

6 Thanks

My thanks to Richard Guy [3] and Paulo Ribenboim [5, 6] for pointing out this problem in their books, and the makers of PARI [1] for the use of their wonderful program.

References

[1] C. Batut, K. Belabas, D. Bernardi, Henri Cohen, and M. Olivier, User’s guide to PARI-GP, Version 2 (1999).

[2] Ronald L. Graham, A Fibonacci-like sequence of composite numbers, Mathematics Magazine 37 (1964), 322-324.

[3] Richard K. Guy, Unsolved Problems in Number Theory, Second Edition (1994), 11, 252.

[4] Donald E. Knuth, A Fibonacci-like sequence of composite numbers, Mathematics Magazine 63 (1990), 21-25.

[5] Paulo Ribenboim, The Little Book of Big Primes (1991), 178.

[6] Paulo Ribenboim, The New Book of Prime Number Records (1996), 367.

[7] R. J. Simpson, Regular coverings of the integers by arithmetic progressions, Acta Arithmetica, 45 (1985), 145-152.

[8] Herbert S. Wilf, Letters to the Editor, Mathematics Magazine 63 (1990),