\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen, filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
 \vskip 1cm{\LARGE\bf A New Fibonacci-like Sequence of Composite Numbers}
 \vskip 1cm
 \large

M. Vsemirnov\footnote{Supported in part
by Russian Foundation for Basic Research
(grant no.~02-01-00089)}\\
Sidney Sussex College \\ 
Sidney Street \\
Cambridge, England CB2 3HU \\
United Kingdom \\
\href{mailto:mv254@dpmms.cam.ac.uk}{\tt mv254@dpmms.cam.ac.uk}\\
and       \\
Steklov Institute of Mathematics \\
27, Fontanka \\
St. Petersburg, 191023 \\
Russia  \\
\href{mailto:vsemir@pdmi.ras.ru}{\tt vsemir@pdmi.ras.ru}
\end{center}


\vskip .2 in
\begin{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$.
\end{abstract}


\newtheorem{theorem}{Theorem}



In this note we consider Fibonacci-like sequences, i.e., the
sequences $\{ A_n\}$  satisfying  the recurrence relation
 \begin{equation}
  \label{eq:fiblike}
   A_n=A_{n-1}+A_{n-2},\qquad n\ge 2.
 \end{equation}
Ronald Graham \cite{G} proved that there exist relatively prime
positive integers $a$ and $b$ such that the sequence $\{ A_n \}$
defined by (\ref{eq:fiblike}) and the initial conditions
 \begin{equation}
  \label{eq:init}
   A_0=a, A_1=b
 \end{equation}
contains no prime number. He also provided an example of such a
pair $(a, b)$. Both numbers had 34 decimal digits. Donald Knuth
\cite{K} described an improvement of Graham's method and found a
17-digit pair. Soon after, Herbert Wilf \cite{W} discovered a
smaller 17-digit pair. Knuth's paper \cite{K} 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 \cite{N} made a significant progress.
Developing Knuth's idea and using an extensive computer search he
found the following 12-digit pair:
 $$
   a=407389224418, \quad b=76343678551.
 $$
The aim of this note is to provide a new Fibonacci-like sequence
with even smaller initial values. We prove

\begin{theorem}
Let $\{A_n\}$, $n\ge 0$, be defined by {\rm
(\ref{eq:fiblike})--(\ref{eq:init})} with the following relatively
prime initial values:
 $$
   a=106276436867, \quad b=35256392432.
 $$
Then $\{A_n\}$ contains no prime number.
\end{theorem}

\begin{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:
\begin{itemize}
  \item[(i)] each $p_i$ is a prime;
  \item[(ii)] $p_i$ divides $F_{m_i}$, the $m_i$-th Fibonacci
  number;
  \item[(iii)] the congruences
 \begin{equation}
 \label{eq:cover}
 x\equiv r_i \pmod{m_i}
 \end{equation}
cover the integers, i.e., for any integer $x$ there is some $i$,
$1\le i\le 17$, such that $x\equiv r_i$ (mod $m_i$).
\end{itemize}
%
Next, we define $a$ and $b$ as follows:
 \begin{eqnarray*}
   a &\equiv &  c_i F_{m_i-r_i}   \pmod{p_i} , \quad i=1,\dots,17; \\
   b &\equiv &  c_i F_{m_i-r_i+1} \pmod{p_i}, \quad i=1,\dots,17.
 \end{eqnarray*}
In particular,
  $$
  A_n \equiv c_i F_{n+m_i-r_i} \pmod{p_i}.
  $$
Using (ii) and the divisibility property $F_m \mid F_{mk}$ we
deduce that $p_i$ divides $A_n$ if $n\equiv r_i$ (mod $m_i$) Since
$A_n$ is an increasing sequence for $n\ge 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  \cite{K}.

Now we list the  desired quadruples. We arrange them into three
groups, namely,
$$
\begin{array}{ccccc}
(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)
\end{array}
$$
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,\dots,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 (\ref{eq:cover}).
\end{proof}

Graham \cite{G}, Knuth \cite{K} and Wilf \cite{W} 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\equiv 3,5$ (mod $6$), and the congruences in the third group
cover all integers $x\equiv 0$  (mod $6$). The second group covers
$x\equiv 1,4$ (mod $6$), but in contrast to the previous covering
systems the second group itself  is not enough to cover all
integers $x\equiv 2$ (mod $6$). However, our congruences
(\ref{eq:cover}) 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.

\begin{thebibliography}{9}
\bibitem{G}
R. L. Graham, A Fibonacci-like sequence of composite numbers,
\emph{Math. Mag.} {\bf 37} (1964), 322--324.

\bibitem{K}
D. E. Knuth, A Fibonacci-like sequence of composite numbers,
\emph{Math. Mag.} {\bf 63} (1990), 21--25.

\bibitem{N}
J. W. Nicol, A Fibonacci-like sequence of composite numbers,
\emph{Electron. J. Combin.} {\bf 6} (1999), \#R44.

\bibitem{W}
H. S. Wilf, Letters to the editor, \emph{Math. Mag.} {\bf 63}
(1990), 284.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B39; Secondary 11N99.

\noindent \emph{Keywords:} Fibonacci-like recurrence, composite
numbers.

\bigskip
\hrule
\bigskip

\noindent Received August 2 2004;
revised version received October 11 2004.
Published in {\it Journal of Integer Sequences}, October 11 2004.

\bigskip
\hrule
\bigskip

\noindent Return to \htmladdnormallink{Journal of Integer
Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip
.1in

\end{document}