A New Fibonacci-like Sequence of Composite Numbers

M. Vsemirnov^{1} Sidney Sussex College Sidney Street Cambridge, England CB2 3HU United Kingdom

                     mv254@dpmms.cam.ac.uk

and Steklov Institute of Mathematics 27, Fontanka St. Petersburg, 191023 Russia

                      vsemir@pdmi.ras.ru

Abstract We find a new Fibonacci-like sequence of composite numbers and reduce the current

record for the starting values to A_{0} = 106276436867 and A_{1} = 35256392432.

In this note we consider Fibonacci-like sequences, i.e., the sequences {A_{n}} satisfying the recurrence relation

A_{n} = A_{n−1} + A_{n−2}, n ≥ 2. (1)

Ronald Graham [1] proved that there exist relatively prime positive integers a and b such that the sequence {A_{n}} defined by (1) and the initial conditions

A_{0} = a, A_{1} = b  (2)

contains no prime number. He also provided an example of such a pair (a, b). Both numbers had 34 decimal digits. Donald Knuth [2] described an improvement of Graham’s method and found a 17-digit pair. Soon after, Herbert Wilf [4] discovered a smaller 17-digit pair.

1Supported in part by Russian Foundation for Basic Research (grant no. 02-01-00089)

Knuth’s paper [2] ends with a challenge asking for substantially smaller starting values, say fewer than ten digits each. Although this bound has not been achieved yet, John Nicol [3] made a significant progress. Developing Knuth’s idea and using an extensive computer search he found the following 12-digit pair:

a = 407389224418, b = 76343678551.

The aim of this note is to provide a new Fibonacci-like sequence with even smaller initial values. We prove

Theorem 1. Let {A_{n}}, n ≥ 0, be defined by (1)–(2) with the following relatively prime initial values:

a = 106276436867, b = 35256392432.

Then {A_{n}} contains no prime number.

Proof. The idea of the proof in its essence is Knuth’s modification of Graham’s method. First, we find 17 quadruples (p_{i}, m_{i}, r_{i}, c_{i}) with the following properties:

(i) each p_{i} is a prime;

(ii) p_{i} divides F_{m_{i}}, the m_{i}-th Fibonacci number;

(iii) the congruences

x ≡ r_{i} (mod m_{i})  (3)

cover the integers, i.e., for any integer x there is some i, 1 ≤ i ≤ 17, such that x ≡ r_{i} (mod m_{i}).

Next, we define a and b as follows:

a ≡ c_{i}F_{m_{i}−r_{i}} (mod p_{i}), i = 1, …, 17;
b ≡ c_{i}F_{m_{i}−r_{i}+1} (mod p_{i}), i = 1, …, 17.

In particular,

A_{n} ≡ c_{i}F_{n+m_{i}−r_{i}} (mod p_{i}).

Using (ii) and the divisibility property F_{m} | F_{mk} we deduce that p_{i} divides A_{n} if n ≡ r_{i} (mod m_{i}) Since A_{n} is an increasing sequence for n ≥ 1 and all prime divisors p_{i} are relatively small, condition (iii) implies that {A_{n}} contains only composites.

The role of the parameters c_{i} is to minimize the solution corresponding to a given covering system. They were found by a method similar to that described by Knuth [2].

Now we list the desired quadruples. We arrange them into three groups, namely,

(3, 4, 3, 2)  (2, 3, 1, 1)  (5, 5, 4, 2)
(7, 8, 5, 3)  (17, 9, 2, 5)  (11, 10, 6, 6)
(47, 16, 9, 34)  (19, 18, 14, 14)  (61, 15, 12, 29)
(23, 24, 17, 6)  (107, 36, 8, 19)  (31, 30, 0, 21)
(1103, 48, 33, 9) (181, 90, 80, 58)  (41, 20, 18, 11)
(541, 90, 62, 185) (2521, 60, 48, 306)

As these quadruples are listed, the rest of the proof is a straightforward verification. Notice that the least common multiple of m_{i}, i = 1, …, 17, equals 720. Thus, to prove (iii) it is enough to check that any number between 1 and 720 is covered by at least one congruence (3).

Graham [1], Knuth [2] and Wilf [4] used similar covering systems with primes 2207, 1087, 4481, 53, 109, 5779 instead of 23, 1103, 107, 181, 541, while Nicol’s construction involved primes 53, 109, 5779 instead of 107, 181, 541. We notice that the above congruences in our first group cover all integers x ≡ 3, 5 (mod 6), and the congruences in the third group cover all integers x ≡ 0 (mod 6). The second group covers x ≡ 1, 4 (mod 6), but in contrast to the previous covering systems the second group itself is not enough to cover all integers x ≡ 2 (mod 6). However, our congruences (3) based on the three groups all together still cover the set of integers.

The interesting problem is how far from the optimal solution we are. It is possible to keep primes p_{i} and vary residues r_{i} still preserving condition (iii). Further analysis of these cases gives no better choice of (a, b). However, it might be possible to find a smaller pair (a, b) exploiting a covering system based on another set of primes.

References

[1] R. L. Graham, A Fibonacci-like sequence of composite numbers, Math. Mag. 37 (1964), 322–324.

[2] D. E. Knuth, A Fibonacci-like sequence of composite numbers, Math. Mag. 63 (1990), 21–25.

[3] J. W. Nicol, A Fibonacci-like sequence of composite numbers, Electron. J. Combin. 6 (1999), #R44.

[4] H. S. Wilf, Letters to the editor, Math. Mag. 63 (1990), 284.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11N99. Keywords: Fibonacci-like recurrence, composite numbers.

Received August 2 2004; revised version received October 11 2004. Published in Journal of Integer Sequences, October 11 2004.

Return to Journal of Integer Sequences home page.