\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}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
A New Kind of Fibonacci-Like Sequence \\
\vskip .11in
of Composite Numbers
}
\vskip 1cm
\large
Dan Ismailescu\\
Department of Mathematics \\
Hofstra University\\
103 Hofstra University \\
Hempstead, NY 11549 \\
USA\\
\href{mailto:dan.p.ismailescu@hofstra.edu}{\tt dan.p.ismailescu@hofstra.edu}\\
\ \\
Jaesung Son\\
Ridgewood High School\\
627 East Ridgewood Ave\\
Ridgewood, NJ 07450 \\
USA\\
\href{mailto:sonjaesung@gmail.com}{\tt sonjaesung@gmail.com }\\
\end{center}
\vskip .2 in
\begin{abstract}
An integer sequence $(x_n)_{n\ge 0}$ is said to be {\it Fibonacci-like} if it satisfies the binary recurrence relation
\begin{equation*}
x_n=x_{n-1}+x_{n-2}, \quad n\geq 2.
\end{equation*}
We construct a new type of Fibonacci-like sequence of composite numbers.
\end{abstract}
\section{The problem and previous results}\label{fibo}
In this paper we consider {\it Fibonacci-like} sequences, that is, sequences $({x_n})_{n=0}^\infty$ satisfying the binary recurrence relation
\begin{equation}\label{recrel}
x_n=x_{n-1}+x_{n-2}, n\geq 2.
\end{equation}
If $x_0=0$ and $x_1=1$ then $x_n=F_n$, the classical Fibonacci sequence. Similarly, when $x_0=2$ and $x_1=1$ then $x_n=L_n$, the Lucas sequence.
Graham \cite{Graham} proved that there exist relatively prime positive integers $x_0$ and $x_1$ such
that the sequence $({x_n})_{n=0}^\infty$ defined by the recurrence above contains no prime numbers;
$x_0$ and $x_1$ have 33 and 34 digits, respectively.
Knuth \cite{Knuth} improved on Graham's method and found a 17-digit pair.
Soon after, Wilf \cite{Wilf} discovered a smaller 17-digit pair. Nicol \cite{Nicol} refined Knuth's idea and
found a 12-digit pair. Finally, Vsemirnov \cite{Vsemirnov} found a smaller pair of 12 and 11 digits: $x_0=106276436867$, $x_1=35256392432$.
Let us describe the common idea used in proving these results. Start by looking for a finite set
of quadruples $(p_i, m_i, r_i,c_i)$, $1\le i\le t$ with the following properties:
\begin{itemize}
\item[(a)]{each $p_i$ is a prime;}
\item[(b)]{every $p_i$ divides $F_{m_i}$, the $m_i$-th Fibonacci number;}
\item[(c)]{every positive integer $n$ satisfies a congruence $n\equiv r_i$ (mod $m_i$) for some $i=1,\,2,\ldots,\,t$.
In other words, $\{(r_i,m_i)\}_{i=0}^{i=t}$ is a {\it covering system of the integers.}}
\end{itemize}
Next, define $x_0$ and $x_1$ as follows:
\begin{equation}\label{define}
x_0\equiv c_iF_{m_i-r_i}\pmod{p_i} \qquad \text {and} \quad x_1\equiv c_iF_{m_i-r_i+1}\pmod{p_i} \quad \text{for}\,\, i=1,\,2,\,\ldots,\, t.
\end{equation}
From the recurrence relation \eqref{recrel} it follows that in general, $x_n\equiv c_iF_{n+m_i-r_i}$ (mod $p_i$). The divisibility property $F_m\,|\,F_{sm}$ and condition (b) imply that $p_i\,|\,x_n$ if $n\equiv r_i$ (mod $m_i$).
Since $x_n$ is an increasing sequence and all primes $p_i$ are relatively small, condition (c) guarantees that $({x_n})_{n=0}^\infty$ contains only composite numbers. The role of the parameters $c_i$ is to minimize the solution corresponding to a given covering system.
As mentioned earlier, the current record is due to Vsemirnov whose construction is based on the following set of $t=17$ quadruples $(p_i, m_i, r_i, c_i)$:
\medskip
\begin{table}[ht]
\begin{tabular} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$p_i$&3&2&5&7&17&11&47&19&61&23&107&31&1103&181&41&541&2521\\
\hline
$m_i$&4&3&5&8&9&10&16&18&15&24&36&30&48&90&20&90&60\\
\hline
$r_i$&3&1&4&5&2&6&9&14&12&17&8&0&33&80&18&62&48\\
\hline
$c_i$&2&1&2&3&5&6&34&14&29&6&19&21&9&58&11&185&306\\
\hline
\end{tabular}
\bigskip
\caption{Vsemirnov's quadruples}
\end{table}
Graham, Knuth and Wilf used similar covering systems except with primes $2207$, $1087$, $4481$, $53$, $109$ and $5779$ instead of $23$, $1103$, $107$, $181$ and $541$.
Nicol used primes $53$, $109$, $5779$ instead of $107$, $181$, $541$.
A major factor in deciding the size of a solution is the product of the primes in the covering system: $P=\prod_{i=1}^t p_i$. The smaller the value of $P$, the greater the chance to find a smaller solution. Of all constructions mentioned above, Vsemirnov's attains the smallest $P$. It is not known whether a better covering system can be found.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A new construction}
We note that Izotov \cite{Izotov} was the first to propose an alternative approach to a different problem, namely that of construction of Sierpi\'{n}ski numbers, for which the only known solutions involved the use of covering systems. In fact, Erd\H{o}s \cite[Section F13]{Guy} conjectured that Sierpi\'{n}ski numbers could only be constructed by the use of covering systems.
Similarly, all known examples of Fibonacci-like sequences of composite numbers are based on the existence of a finite covering set of primes $\{p_1,p_2,\ldots,p_t\}$. In other words, all examples mentioned in the previous section have the property that for every positive integer $n$, there exists an $i\in\{1,2,,\ldots,t\}$ with $x_n\equiv 0$ (mod $p_i$).
In this paper we construct a Fibonacci-like sequence of composite numbers for which such a covering set does not appear to exist.
Our approach can be summarized as follows:
On one hand, we are going to choose two relatively prime positive integers $x_0$ and $x_1$, such that for every
nonnegative integer $n$, $x_{2n+1}$ is equal to the product of two integers greater than $1$, both of which can be written explicitly in terms of $n$, $x_0$ and $x_1$.
On the other hand, we are going to find a finite set of prime numbers $\{p_1,p_2,\ldots,p_t\}$ such that for every nonnegative integer $n$,
$x_{2n}\equiv 0$ (mod $p_i$) for some $i\in\{1,2,\ldots,t\}$.
We will thus obtain the desired Fibonacci-like sequence of composite numbers. Notice that there are different reasons
why $x_n$ is composite depending on the parity of $n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}\label{odd}
Consider the sequence given by $x_0=p^2+q^2$, $x_1=2pq+q^2$, $x_n=x_{n-1}+x_{n-2}$ for all $n\ge 2$, where $p$ and $q$ are integers.
Then for every $n\ge 0$ we have
\begin{equation}\label{eqodd}
x_{2n+1}=(pF_n+qF_{n+1})(pL_n+qL_{n+1}).
\end{equation}
In particular, if $p\ge 1$ and $q\ge 2$, then $x_{2n+1}$ is composite for all $n\ge 0$.
\end{theorem}
\begin{proof}
It is known that the Fibonacci numbers can be written in matrix form as below
\begin{equation*}
\begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix} =
{\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}}^n \quad {\rm for\,\, all\,\,} n\ge 1.
\end{equation*}
Using the fact that $A^{m+n}=A^mA^n$ with $A=\bigl[\begin{smallmatrix}1&1\\ 1&0
\end{smallmatrix} \bigr]$ it follows that
\begin{equation*}
\begin{bmatrix}
F_{m+n+1} & F_{m+n} \\
F_{m+n} & F_{m+n-1}
\end{bmatrix}=
\begin{bmatrix}
F_{m+1} & F_m \\
F_m & F_{m-1}
\end{bmatrix}\cdot
\begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix} \quad {\rm from\,\, which}
\end{equation*}
\begin{equation*}\label{mn}
F_{m+n+1}=F_{m+1}F_{n+1}+F_mF_n.
\end{equation*}
In particular, taking $m=n$ and $m=n-1$ respectively, we obtain
\begin{align}
&F_{2n+1}=F^2_{n+1}+F_n^2,\label{2n+1}\\
&F_{2n}=2F_nF_{n+1}-F^2_n\label{2n}.
\end{align}
It is easy to prove by induction that $x_n=x_0F_{n-1}+x_1F_n$\label{x_n}. It follows that
\begin{equation*}
x_{2n+1}=x_0F_{2n}+x_1F_{2n+1}
\end{equation*}
which after using equalities \eqref{2n+1} and \eqref{2n} gives
\begin{equation}\label{xodd}
x_{2n+1}=x_0(2F_nF_{n+1}-F_n^2)+x_1(F_{n+1}^2+F_n^2)=(x_1-x_0)F_n^2+2x_0F_nF_{n+1}+x_1F_{n+1}^2.
\end{equation}
Regard the right hand term in the above equation as a quadratic form in the variables $F_n$ and $F_{n+1}$.
We want this quadratic form to be reducible over the integers for all $n$, which is equivalent to requiring
the discriminant $\Delta=x_0^2-(x_1-x_0)x_1$ to be a perfect square.
In other words we want to choose $x_0$ and $x_1$ as solutions of the diophantine equation
\begin{equation}\label{perfectsquare}
x_0^2+x_0x_1-x_1^2=k^2.
\end{equation}
It is straightforward to check that $x_0=p^2+q^2$, $x_1=2pq+q^2$ is a solution of the above equation.
Indeed, with the above choices for $x_0$ and $x_1$ we have
\begin{align*}
x_0^2+x_0x_1-x_1^2&=(p^2+q^2)^2+(p^2+q^2)(2pq+q^2)-(2pq+q^2)^2=\\
&=p^4+2p^3q-p^2q^2-2pq^3+q^4=(p^2+pq-q^2)^2.
\end{align*}
This solution can be obtained by using the techniques for solving the general equation $ax^2+bxy+cy^2=k^2$;
the interested reader may consult \cite[Chapter XIII, pp.\ 404--409]{Dickson}. This explains our choices for $x_0$ and $x_1$.
Substituting now $x_0=p^2+q^2$ and $x_1=2pq+q^2$ into \eqref{xodd} we obtain
\begin{align*}
x_{2n+1}&=(2pq-p^2)F_n^2+2(p^2+q^2)F_nF_{n+1}+(2pq+q^2)F^2_{n+1}=\\
&=p^2(2F_nF_{n+1}-F_n^2) + pq(2F_n^2+2F_{n+1}^2) + q^2(2F_nF_{n+1} + F_{n+1}^2)=\\
&=p^2F_n(2F_{n+1}-F_n) + 2pq(F_n^2+F_{n+1}^2) + q^2F_{n+1}(2F_n + F_{n+1}).
\end{align*}
We use now some basic identities relating the Fibonacci and the Lucas numbers.
\begin{align*}
2F_{n+1} - F_n &= F_{n+1} + (F_{n+1} - F_n) = F_{n+1} + F_{n-1} = L_n.\\
2F_n + F_{n+1} &= F_n + (F_n + F_{n+1}) = F_n + F_{n+2} = L_{n+1}.\\
2(F_n^2+F_{n+1}^2)&=F_n(2F_n+F_{n+1})+F_{n+1}(2F_{n+1}-F_n)=F_nL_{n+1}+F_{n+1}L_n.
\end{align*}
Substituting these into the last equality, we obtain
\begin{equation*}
x_{2n+1}=p^2F_nL_n+pq(F_nL_{n+1}+F_{n+1}L_n)+q^2F_{n+1}L_{n+1}= (pF_n + qF_{n+1})\cdot(pL_n + qL_{n+1}).
\end{equation*}
Thus, equation \eqref{eqodd} is satisfied. If $p\ge 1$ and $q\ge 2$ it follows that for all nonnegative integers $n$ we have that $pF_n + qF_{n+1}\ge q\ge 2$ and $pL_n +qL_{n+1}>p+q\ge 3$. It follows that $x_{2n+1}$ is always composite. The proof is complete.
\end{proof}
From Theorem \ref{odd} it follows that if one chooses $x_0=p^2+q^2$ and $x_1=2pq+q^2$, then for every $n\ge 0$ we have that $x_{2n+1}$ is composite. It remains to ensure that for every $n\ge 0$, $x_{2n}$ is also composite. In order to achieve this, we construct a finite partial covering set as described below.
We are looking for a collection of quadruples $\{(p_i,m_i,r_i,c_i)\}^{i=t}_{i=1}$ such that
\begin{itemize}
\item[(a)] {each $p_i$ is a prime;}
\item[(b)] {every $p_i$ divides $F_{m_i}$, the $m_i$-th Fibonacci number;}
\item[(c)] {every even positive integer $2n$ satisfies at least a congruence $2n\equiv r_i$ (mod $m_i$) for some $i=1,\,2,\ldots,\,t$.
In other words, $\{(r_i,m_i)\}_{i=0}^{i=t}$ is a partial covering system, as it covers all even integer values.}
\end{itemize}
For every $1\le i\le t$, we have $1\le c_i \le p_i-1$. These values are going to come into play later on, as we will require
a certain system of congruences to be compatible.
Suppose we found such a set of quadruples. Choose $x_0$ and $x_1$ such that
\begin{equation}\label{choicex0x1}
x_0 \equiv c_iF_{m_i-r_i}\pmod{p_i},\quad x_1 \equiv c_iF_{m_i-r_i+1} \pmod{p_i}\quad \text{for all}\,\, 1\le i\le t.
\end{equation}
Let $n\ge 0$ and let $1\le i\le t$ be such that $2n\equiv r_i$ (mod $m_i$). The existence of such $i$ is guaranteed by condition (b).
From \eqref{x_n}, we have
\begin{align*} x_{2n} = x_0F_{2n-1} + x_1F_{2n} &\equiv c_i(F_{m_i-r_i}\cdot F_{2n-1} + F_{m_i-r_i+1}\cdot F_{2n})\pmod{p_i}\\
&\equiv c_i\, F_{2n+m_i-r_i} \pmod{p_i} \\
&\equiv c_i \, F_{sm_i} \pmod{p_i} \\
& \equiv 0 \pmod{p_i}.
\end{align*}
Thus, $x_{2n}\equiv 0$ (mod $p_i$) and therefore composite. There is however one major difficulty in finding a partial covering system with the properties (a), (b) and (c) listed above, as every odd prime $p_i$ has to satisfy the congruence $p_i\equiv 1$ (mod $4$).
Let us explain why that is the case. First, we need the following simple result.
\begin{lemma}\label{1mod4}
For any positive odd integer $m$, the Fibonacci number $F_m$ has no prime factors of the form $4l+3$.
\end{lemma}
\begin{proof}
Let $m$ be odd and let $p\,|\,F_m$.
From Cassini's identity, we have
$F_{m+1}^2-F_mF_{m+2} = (-1)^m$, which after reducing modulo $p$ gives
$F_{m+1}^2 \equiv -1$ (mod $p$).
This implies that $-1$ is a quadratic residue modulo $p$. By the quadratic reciprocity law this is true only when $p \equiv 1$ (mod 4).
\end{proof}
Recall that in Theorem \ref{odd} we chose $x_0$ and $x_1$ such that $x_0^2 + x_0x_1 - x_1^2 = k^2$. On the other hand, we selected $x_0$ and $x_1$
as in \eqref{choicex0x1}. It follows that for every $1\le i\le t$ we have that
\begin{equation}
c_i^2(F_{m_i-r_i}^2 + F_{m_i-r_i}\cdot F_{m_i-r_i+1} - F_{m_i-r_i+1}^2) \equiv k^2 \pmod{p_i}
\end{equation}
Using Cassini's identity again, the above congruence can be simplified to $c_i^2\cdot (-1)^{m_i-r_i+1} \equiv k^2 \pmod {p_i}$.
In particular, $(-1)^{m_i-r_i+1}$ is a quadratic residue modulo $p_i$ for every $1 \le i \le t$.
We want that for every $n\ge 0$, the congruence
$2n\equiv r_i\pmod{m_i}$ holds for some $1\le i\le t$.
If $m_i$ is even, then $r_i$ is even as well, and therefore
$(-1)^{m_i-r_i+1}=-1$, which is a quadratic residue modulo $p_i$ if and
only if $p_i\equiv 1\pmod{4}$. If $m_i$ is odd, then condition (b)
states that $p_i\,|\,F_{m_i}$, and hence $p_i\equiv 1$ (mod $4$)
follows from Lemma \ref{1mod4}.
Hence, none of the primes $p_i$ in the partial covering system with
properties (a), (b) and (c) can be of the form $4l+3$.
Consider the set $\{(p_i, m_i, r_i, c_i)\}_{i=1}^{i=30}$ given in Table \ref{table2}. It is straightforward to check that this system of quadruples has the desired properties.
\medskip
\begin{table}[ht]\label{table2}
\begin{centering}
\begin{tabular} {|c|c|c|c|}
\hline
$p_i$ & $m_i$ & $r_i$ & $c_i$\\
\hline
2&3&1&1\\
\hline
5&5&1&2\\
\hline
13&7&1&5\\
\hline
17&9&3&11\\
\hline
29&14&2&5\\
\hline
41&20&4&3\\
\hline
61&15&2&41\\
\hline
181&90&8&46\\
\hline
241&120&14&109\\
\hline
281&28&4&207\\
\hline
421&21&3&171\\
\hline
541&90&38&243\\
\hline
1009&126&90&294\\
\hline
1601&80&34&1259\\
\hline
2161&40&10&1706\\
\hline
\end{tabular}
\qquad\qquad
\begin{tabular} {|c|c|c|c|}
\hline
$p_i$ & $m_i$ & $r_i$ & $c_i$\\
\hline
2521&60&20&636\\
\hline
3041&80&74&790\\
\hline
8641&360&18&4664\\
\hline
20641&120&110&1405\\
\hline
31249&126&42&901\\
\hline
103681&72&54&80856\\
\hline
109441&45&23&16635\\
\hline
141961&35&12&12156\\
\hline
721561&420&180&529617\\
\hline
1461601&252&186&970625\\
\hline
35239681&63&6&25860534\\
\hline
764940961&252&0&562105967\\
\hline
8288823481&105&33&83463210\\
\hline
10783342081&180&162&7785411056\\
\hline
571385160581761&504&222&49367403415248\\
\hline
\end{tabular}
\bigskip
\caption{A finite partial covering system with no primes $\equiv 3\pmod{4}$}
\end{centering}
\end{table}
\medskip
\noindent Let us notice that in order to check condition (c), it suffices to test the even numbers
$\le 5040$. This is indeed the case since $5040$ is the least common multiple of all the $m_i$, $1\le i\le 30$.
We are now in position to state the main result of this paper.
\begin{theorem}\label{mainthm}
Let $p=1$ and $q=12951150255508108245872399074061259209531943793351-\\
2025195406541068394745828231264515958532145970461367703231950382110924410768870$.
Define a sequence $(x_n)_{n\ge 0}$ by $x_0=p^2+q^2$, $x_1=2pq+q^2$, $x_n=x_{n-1}+x_{n-2}$, for all $n\ge 2$.
Then $\gcd(x_0, x_1)=1$ and $x_n$ is composite for all $n\ge 0$.
\end{theorem}
\begin{proof}
By our choice of $x_0$ and $x_1$, Theorem \ref{odd} immediately implies that $x_{2n+1}$ is composite for every integer $n\ge 0$.
We claim that for every $n\ge 1$, $x_{2n}$ has a factor in the set $\{p_1, p_2, \ldots, p_{30}\}$,
where the primes are those in Table \ref{table2}. Indeed, let us first choose $x_0$ and $x_1$ according to \eqref{choicex0x1}
\begin{equation*}
x_0 \equiv c_iF_{m_i-r_i}\pmod{p_i},\quad x_1 \equiv c_iF_{m_i-r_i+1} \pmod{p_i}\quad \text{for all}\,\, 1\le i\le 30,
\end{equation*}
where $(p_i, m_i, r_i, c_i)$ are those given in Table \ref{table2}.
Since $p=1$, $x_0=p^2+q^2$ and $x_1=2pq+q^2$, these congruences can be written as
\begin{equation}\label{q}
1+q^2 \equiv c_iF_{m_i-r_i}\pmod{p_i},\quad 2q+q^2 \equiv c_iF_{m_i-r_i+1} \pmod{p_i}\quad \text{for all}\,\, 1\le i\le 30.
\end{equation}
\begin{table}[ht]
\begin{centering}
\begin{tabular} {|c|c|}
\hline
$p_i$ & $ q \bmod{p_i}$ \\
\hline
2&0\\
\hline
5&0\\
\hline
13&0\\
\hline
17&11\\
\hline
29&20\\
\hline
41&34\\
\hline
61&55\\
\hline
181&149\\
\hline
241&134\\
\hline
281&45\\
\hline
421&140\\
\hline
541&307\\
\hline
1009&818\\
\hline
1601&1347\\
\hline
2161&799\\
\hline
\end{tabular}
\qquad\qquad
\begin{tabular} {|c|c|}
\hline
$p_i$ & $q\bmod{p_i}$\\
\hline
2521&1934\\
\hline
3041&455\\
\hline
8641&1277\\
\hline
20641&13565\\
\hline
31249&24574\\
\hline
103681&22094\\
\hline
109441&43164\\
\hline
141961&112001\\
\hline
721561&170379\\
\hline
1461601&442479\\
\hline
35239681&5419606\\
\hline
764940961&483887978\\
\hline
8288823481&6095337569\\
\hline
10783342081&54018520\\
\hline
571385160581761&504780818763137\\
\hline
\end{tabular}
\bigskip
\caption{Set of congruences satisfied by the solution of \eqref{q}}
\label{table3}
\end{centering}
\end{table}
The choices of $c_i$ ensure that this system has solutions: in particular, a solution is given by the set of congruences listed in Table \ref{table3}.
The Chinese remainder theorem guarantees that there exists a $q$ that satisfies all the above congruences. The smallest such value is the $129$-digit number mentioned in the statement
of Theorem~\ref{mainthm}.
It remains to argue why we believe this particular sequence $(x_n)_{n\ge 0}$ does not have a finite covering set of primes. Computer verifications show that there are $803$ values of $0\le n\le 200000$ such that $x_n$ has no prime factor $\le 2\times 10^6$ or a prime factor among the primes $p_1,\,p_2,\ldots,\,p_{30}$ given in table \ref{table2}. Moreover, any two such terms are mutually prime.
Also, it can be checked that for these choices for $p$ and $q$, the numbers $pF_{913}+qF_{914}$, $pL_{913}+qL_{914}$, $pF_{943}+qF_{944}$ and $pL_{943}+qL_{944}$ are all primes of lengths $319$, $320$, $326$ and $326$, respectively. Since \eqref{eqodd} gives that $x_{1827}=(pF_{913}+qF_{914})(pL_{913}+qL_{914})$ and $x_{1887}=(pF_{943}+qF_{944})(pL_{943}+qL_{944})$,
it follows that $x_{1827}$ and $x_{1887}$ are both products of exactly two primes, with the least prime factor having lengths 319 and 326, respectively.
As a result, if a finite covering with primes would exist, it has to have at least $803$ primes larger than $2\times 10^6$, and among these, at least two primes of length $319$ or greater. It seems difficult to prove that the least prime factor of $x_n$ is unbounded as $n$ tends to infinity. As already noticed by Filaseta, Finch and Kozek \cite{Filaseta}, this type of question is open even for much simpler sequences such as $F_n$, $5\cdot 2^n+1$ or $11\cdot 5^n-1$.
\end{proof}
\begin{thebibliography}{9}
\bibitem{Dickson} L. E. Dickson, \emph{History of the Theory of Numbers},
Vol.~II: Diophantine Analysis, Chelsea Publishing Co., 1966.
\bibitem{Filaseta} M. Filaseta, C. Finch and M. Kozek, On powers
associated with Sierpi\'{n}ski numbers, Riesel numbers and Polignac's
conjecture, {\it J. Number Theory} {\bf 128} (2008), 1916--1940.
\bibitem{Graham} R. L. Graham, A Fibonacci-like sequence of composite numbers,
{\it Math. Mag.} {\bf 37} (1964), 322--324.
\bibitem{Guy} R. K. Guy, {\it Unsolved Problems in Number Theory} (3rd ed.),
Problem Books in Mathematics, Springer-Verlag, 2004.
\bibitem{Izotov} A. S. Izotov, A note on Sierpi\'{n}ski numbers, {\it Fibonacci Quart.} {\bf 33} (1995), 206--207.
\bibitem{Knuth} D. E. Knuth, A Fibonacci-like sequence of composite numbers,
{\it Math. Mag.} {\bf 63} (1990), 21--25.
\bibitem{Nicol} J. W. Nicol, A Fibonacci-like sequence of composite numbers,
{\it Electron. J. Combin.} {\bf 6} (1999), Research Paper \#R44.
\bibitem{Vsemirnov} M. Vsemirnov, A new Fibonacci-like sequence of
composite numbers, {\it J. Integer Seq.} {\bf 7} (2004),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL7/Vsemirnov/vsem5.html}{Article
04.3.7}.
\bibitem{Wilf} H. S. Wilf, Letters to the Editor, {\it Math. Mag.} {\bf 63} (1990), 284.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11A51, 11B37.
\noindent \emph{Keywords: } Fibonacci-like recurrence, composite numbers, system of covering congruences.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A082411},
\seqnum{A083103},
\seqnum{A083104},
\seqnum{A083105},
\seqnum{A083216}, and
\seqnum{A221286}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 24 2014;
revised version received July 8 2014; July 21 2014.
Published in {\it Journal of Integer Sequences}, July 25 2014.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}