%LaTeX. 7 pages.
\documentclass[12pt]{article}
\pagestyle{myheadings}
%Here I boldfaced the Journal's volume number.
\markright
{\sc the electronic journal of combinatorics \textbf{6} (1999), \#R44\hfill}
\thispagestyle{empty}
\oddsidemargin .3in
\evensidemargin .3in
\textwidth 5.7 in
\vsize=217mm
\begin{document}
\title{A Fibonacci-like sequence of composite numbers}
\author{John W. Nicol\\University of Illinois, Urbana, IL
\\{\small\texttt{nicol@alumni.cs.cmu.edu}}}
\date{\ }
\maketitle
\begin{center}
Submitted: June 17, 1998;
Submitted in revised form: October 12, 1999;
Accepted: November 6, 1999.
\end{center}

\begin{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}\qquad (n\ge 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.
\end{abstract}

\noindent Mathematical Reviews Subject Numbers: 11B39, 11N99.

\section{Introduction}

Ronald Graham \cite{Gr} 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}\qquad (n\ge 2;A_0=a,A_1=b)\]
contains no prime numbers. Graham's pair $(a,b)$ was
\[(331635635998274737472200656430763,151002891108840197118959030549878
5).\]

Donald Knuth \cite{Kn} found the smaller pair
\[(a,b)=(62638280004239857,49463435743205655).\]
Herbert Wilf \cite{Wi} 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
$\left( {p}_{k},{m}_{k},{r}_{k} \right)$ such that
\begin{enumerate}
\item ${p}_{k}$ is prime
\item ${p}_{k} \mid {F}_{n} \iff n \mid {m}_{k}$ ($F_n$ is the Fibonacci
number.)
\item The congruences $x \equiv {r}_{k}$ (mod ${m}_{k}$)
\textit{cover} the integers (i.e., for every number $n$,
there exists a $k, 1 \leq k \leq 18$ such that
$n \equiv {r}_{k} \pmod {{m}_{k}}$)
\end{enumerate}


$$\begin{array}{ccc}
\left( 3,4,1 \right) & \left( 2,3,2 \right) & \left( 5,5,1 \right) \\
\left( 7,8,3 \right) & \left(17,9,4 \right) & \left(11,10,2\right) \\
\left(47,16,7\right) & \left(19,18,10 \right) & \left(61,15,3 \right) \\
\left(2207,32,15\right) & \left(53,27,16 \right) & \left(31,30,24\right) \\
\left(1087,64,31 \right) & \left(109,27,7\right) & \left(41,20,10\right) \\
\left(4481,64,63 \right) & \left(5779,54,52 \right) & \left(2521,60,0 \right)
\end{array}$$
Note that the first column covers all $n \equiv 1 \pmod{2}$, the second
column covers all $n \equiv 2 \pmod{3}$ and $n \equiv 4 \pmod{6}$, and the
third column covers all $n \equiv 0 \pmod{6}$, which
clearly covers all $n$.

Graham then constructed $a$ and $b$ such that

4. ${p}_{k} \mid {A}_{n} \iff n \equiv {r}_{k} \pmod{{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
$\left(b-a,a \right)$ 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
\textit{given the triples} $\left( {p}_{k},{m}_{k},{r}_{k} \right)$.
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
$\left( {p}_{k},{m}_{k},({r}_{k}+4) \right)$, 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
\textit{pairs} $\left( {p}_{k},{m}_{k} \right)$.

\section{Proof of Regularity}

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

\indent
$(3')$. The congruences $x \equiv {r}_{k}$ (mod ${m}_{k}$) are a
\textit{regular covering} (also called an
\textit{irredundant covering}) \cite{Si,Gu} of the integers.

(A \textit{regular covering} is a covering of the integers that has no
unnecessary congruence relations.  Thus a covering
$\{ \left( {m}_{k},{r}_{k} \right) \}$ is regular if there does
not exist an
$i$ such that $\{ \left( {m}_{k},{r}_{k} \right) : k \neq 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 $\left( {m}_{k},{r}_{k} \right)$
form a regular covering.  Assume not (i.e., assume at least one pair
$\left( {m}_{l},{r}_{l} \right)$ 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 $\left( {m}_{l},{r}_{l} \right)$
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 \equiv {c}_{1}$ and ${c}_{2} \pmod{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 \equiv {c}_{1}$ or $n \equiv {c}_{2} \pmod{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 \equiv {c}_{1} \pmod{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 \textit{exact covering} of the integers
$n \equiv c \pmod{2}$
(i.e., if $n \not\equiv c \pmod{2}$, then $n$ is not covered by the
first column).

Let us now assume that a pair $\left( {m}_{l},{r}_{l} \right)$
can be removed from the second column.  This means the second
columns does not cover the integers $n \equiv d$ and $e \pmod{6}$.

Then, by inspection, the
first and second columns do not cover the integers
$n \equiv {d}_{1} \pmod{18}$ and $n \equiv {d}_{2} \pmod{54}$,
where ${d}_{1} \not\equiv {d}_{2} \pmod{3}$, but
${d}_{1} \equiv {d}_{2} \not\equiv c \pmod{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 \equiv {d}_{2} \pmod{54}$.
Thus one of the moduli (5,10,20) and one of the moduli (15,30,60) will
cover the integers $n \equiv {d}_{2} \pmod{54}$, which is clearly false.

So the second column must cover the integers $n \equiv d$ and $e \pmod{6}$,
which means the third column must cover the integers $n \equiv f \pmod{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 $\left( {m}_{k},{r}_{k} \right)$ is regular, and
is in fact regular for all valid choices of the ${r}_{k}$.

\section{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 \equiv 0,2,4,5 \pmod{6}$,
as done in Graham's construction, then the first column need only
cover $n \equiv 1,3 \pmod{6}$.  The first column of Graham's construction
covers $n \equiv 1 \pmod{2}$, which is perhaps overkill.

If we replace the triples $\left( 2207,32,15 \right)$,
$\left( 1087,64,31 \right)$, and $\left( 4481,64,63 \right)$ with
the triples $\left( 23,24,15 \right)$ and $\left( 1103,48,31 \right)$,
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 \equiv 1,3 \pmod {6}$.

It suffices to show that the modulus 48 cannot be removed.  We assume
otherwise; but by inspection, the moduli $\left (4,8,16,24 \right)$ cannot
cover $n \equiv 1,3 \pmod{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.

\section{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 \equiv g \pmod{6}$ and
$n \equiv h \pmod{6}$, where $g$ and $h$ are of the same parity
and $g \not\equiv h \pmod{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 \times 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} \not\equiv g \pmod{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 \times 2 \times 3 \times 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 \times 4 \times 3 \times 2 \times 2 = 240$ ways that the third column can
be chosen.

\section{The Result}
Now, applying Knuth's method \cite{Kn} to each of the
$96 \times 72 \times 240 = 1658880$ cases above,
%(the PARI program used
%can be found at
%\noindent\verb+<http://www.uiuc.edu/ph/www/jnicol/projects/comp_fib.c>+),
we find the smallest values of $a$ and $b$ to be:
%\[(a,b)=(248272649660939,8983542533631)\]
%\[(a,b) = (110860319652,23008837085)\]

\[(a,b)= (407389224418,76343678551)\]
with the triples below:

$$\begin{array}{ccc}
\left( 3,4,3 \right) & \left( 2,3,0 \right) & \left( 5,5,3 \right) \\
\left( 7,8, 1\right) & \left(17,9,5 \right) & \left(11,10,0\right) \\
\left(47,16,5\right) & \left(19,18,8 \right) & \left(61,15,7 \right) \\
\left(23,24,5\right) & \left(53,27,11 \right) & \left(31,30,16\right) \\
\left(1103,48,13 \right) & \left(109,27,2\right) & \left(41,20,14\right) \\
& \left(5779,54,20 \right) & \left(2521,60,4 \right) \\
\end{array}$$


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

\section{Thanks}

My thanks to Richard Guy \cite{Gu} and Paulo Ribenboim \cite{Ri1,Ri2} for
pointing out this problem in their books, and the makers of PARI
\cite{BBCO} for the use of their wonderful program.

\begin{thebibliography}{99}

\bibitem{BBCO} C. Batut, K. Belabas, D. Bernardi,
Henri Cohen, and M. Olivier,
\textit{User's guide to PARI-GP}, Version 2 (1999).
\bibitem{Gr} Ronald L. Graham, A Fibonacci-like sequence
of composite numbers, \textit{Mathematics Magazine} \textbf{37} (1964), 
322-324.
\bibitem{Gu} Richard K. Guy, Unsolved Problems in Number Theory, Second
Edition (1994), 11, 252.
\bibitem{Kn} Donald E. Knuth, A Fibonacci-like sequence of composite
numbers, \textit{Mathematics Magazine} \textbf{63} (1990), 21-25.
\bibitem{Ri1} Paulo Ribenboim,  The Little Book of Big Primes (1991), 178.
\bibitem{Ri2} Paulo Ribenboim,  The New Book of Prime Number Records
(1996), 367.
\bibitem{Si} R. J. Simpson, Regular coverings of the integers by arithmetic
progressions, \textit{Acta Arithmetica}, \textbf{45} (1985), 145-152.
\bibitem{Wi} Herbert S. Wilf, Letters to the Editor, \textit{Mathematics
Magazine} \textbf{63} (1990), 284.

\end{thebibliography}
\end{document}