\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}{-.5in}
\setlength{\textheight}{8.9in}

\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}
\newtheorem{Con}[theorem]{Conditions}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Appending Digits to Generate an Infinite \\
\vskip .1in
Sequence of Composite Numbers
}
\vskip 1cm
\large
Lenny Jones and Daniel White\\
Department of Mathematics \\
Shippensburg University \\
Shippensburg, PA  17257 \\
USA\\
\href{mailto:lkjone@ship.edu}{\tt lkjone@ship.edu}\\
\href{mailto:dw9878@ship.edu}{\tt dw9878@ship.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
Let $D$ be a list of single digits, and let $k$ be a positive integer. We construct an infinite sequence of positive integers by repeatedly appending, in order, one at a time, the digits from the list $D$ to the integer $k$, in one of four ways: always on the left, always on the right, alternating and starting on the left, or alternating and starting on the right. In each of these four situations, we investigate, for various lists $D$, how to find infinitely many positive integers $k$ such that every term of the sequence is composite.
\end{abstract}


\def\ds{\displaystyle}

\numberwithin{equation}{section}
\def\F {{\mathbb F}}
\def\R {{\mathbb R}}
\def\Z {{\mathbb Z}}
\def\N{{\mathbb N}}
\def\Q {{\mathbb Q}}
\def\T {{\tilde T}}
\def\B {{\mathcal B}}
\def\C {{\mathcal C}}
\def\P {{\mathcal P}}
\def\A {{\mathcal A}}
\def\D {{\mathcal D}}

\def\M {{\mathcal M}}
\def\h {{\mathfrak h}}
\def\a {{\mathfrak a}}
\def\l {\left\langle}
\def\r {\right\rangle}
\def\bip{{\mathrm{Bip}}}
\def\K{{\mathcal K}}

\def\d {{\rm det}}

\def\k{{\mathbf k}}
\def\n{{\mathbf n}}
\def\tr{\mathrm{tr}}
\def\red#1 {\textcolor{red}{#1 }}
\def\blue#1 {\textcolor{blue}{#1 }}

\renewcommand{\labelitemii}{$\diamond$}

\def\ds{\displaystyle}\def\C{{\mathcal C}}
\def\Z {{\mathbb Z}}

\vskip .2in

\section{Introduction}\label{Intro}

In a previous paper \cite{L}, the first author proved that, for any digit $d\in \{1,3,7,9\}$, there exist infinitely many positive integers $k$, with $\gcd(k,d)=1$, such that appending $d$ on the right of $k$, any number of times, always gives a composite number. Using similar methods, this paper generalizes this result, with tweaks and alterations along the way as each variation requires. We describe this process more precisely as follows.
Given a list $D=\left[d_1,\ldots, d_t\right]$, where $d_i\in \left\{0,1,\ldots ,9\right\}$, and a positive integer $k$, we construct an infinite sequence $\left\{s_n\right\}_{n=1}^{\infty}$ of positive integers by repeatedly appending, in order, one at a time, the digits from the list $D$ to the integer $k$, in one of four ways: always on the left, always on the right, alternating and starting on the left, or alternating and starting on the right.
For example, if $D=\left[1,7,9\right]$ and $k=a_1a_2\cdots a_q$, where $a_i$ is the $i$th digit of $k$ (reading from left to right), then the sequence $\left\{s_n\right\}_{n=1}^{\infty}$ generated by appending the digits from $D$ to $k$ in an alternating manner, starting on the left, is
\[s_1=1a_1a_2\cdots a_q, \quad s_2=1a_1a_2\cdots a_q7, \quad s_3=91a_1a_2\cdots a_q7, \quad s_4=91a_1a_2\cdots a_q71, \ldots  .\] In each of these four situations, we investigate, for various lists $D$, how to find infinitely many positive integers $k$ such that every term of the sequence $\left\{s_n\right\}_{n=1}^{\infty}$ is composite. We can also assume that the list $D=\left[d_1,\ldots, d_t\right]$ is minimal in the sense that there is no $j<t$ such that the list $[d_1,\ldots ,d_j]$ would generate the same sequence as $D$. For example, the sequence generated using the list $[1,3,1,3]$ is the same as the sequence generated using the sublist $[1,3]$, and so in this case we let $D=[1,3]$. There are clearly trivial situations which can arise, such as appending the digits from $D=[3,9]$ to any $k$ that is a multiple of $3$. For the most part, we do not concern ourselves with excluding such trivial situations, since our methods can be modified easily, if necessary, to avoid them completely. An illustration of such a modification is given in Section \ref{SubSectionL5}. We summarize the results of this paper in Theorem \ref{Thm:Main}. Because of the similarities of the techniques used, we give details only for certain values of $t$. We point out that both Maple and Magma were used extensively in our investigation.
\begin{theorem}\label{Thm:Main}
 Let $D=\left[d_1,\ldots, d_t\right]$, where $d_i\in \left\{0,1,\ldots ,9\right\}$.
 \begin{enumerate}
   \item For $t\le 10$, there exist infinitely many positive integers $k$ such that repeatedly appending the digits one at a time in order from the list $D$, either on the left, or on the right of $k$, generates an infinite sequence, all of whose terms are composite.
\item For $t\le 10$, $t\ne 7,9$, there exist infinitely many positive integers $k$ such that repeatedly appending the digits in an alternating manner, one at a time in order from the list $D$, starting either on the left, or on the right of $k$, generates an infinite sequence, all of whose terms are composite.
\end{enumerate}
\end{theorem}


\section{The General Strategy}
The main tool used in our investigation is the following concept, which is due to Erd\H{o}s \cite{E}.
\begin{definition}\label{Def:Covering}
A (finite) {\it covering system}, or simply a {\it covering}, of the integers is a system of congruences $n\equiv r_i \pmod{m_i}$, with $1\le i \le s$, such that every integer $n$ satisfies at least one of the congruences.
\end{definition}

\begin{remark}\label{Rem:Covering necessity}
 It is straightforward to show that in any covering $\left\{n\equiv r_i \pmod{m_i} \right\}$, where $1\le i \le s$, we have that $\sum_{i=1}^s\frac{1}{m_i}\ge 1$. This condition, however, is not sufficient.
\end{remark}



To prove Theorem \ref{Thm:Main} for each value of $t$ in each part, we use a covering $\{r_i \pmod{m_i}\}$ of the integers $n$, the indices of the sequence $\left\{s_n\right\}_{n=1}^{\infty}$ (as defined in Section \ref{Intro}), and a set of corresponding primes $\P$, such that $p_i\in \P$ divides $s_n$ when $n\equiv r_i\pmod{m_i}$. In addition, the moduli in the covering, and the set $\P$ need to satisfy certain conditions which are given in Sections \ref{Section:OnlyRight} and \ref{Section:Alternating}. These conditions differ slightly, depending on whether we are appending on just one side, or in an alternating manner. In all situations, however, finding the desired values of $k$ requires knowing the prime factors of integers of the form $10^m-1$.
To find these values of $k$ for each value of $t$ in Theorem \ref{Thm:Main}, we first use Maple, together with tables of prime divisors of $10^m-1$ \cite{MK,K}, to construct a set of possible moduli for the covering, within the constraints of our conditions. Then we use a Magma program \cite{BC}, which employs a ``greedy" algorithm, to construct the residues for the covering. If, at any stage, there is more than one optimal choice for a residue, Magma chooses one at random. The covering allows us to construct a system of congruences in $k$, which can be solved easily using the Chinese remainder theorem. Most of these computations were done on an Intel Core i7 computer with 9 gigabytes of memory.

It will be convenient throughout the article to represent a covering and the associated set of primes using a set $\C$ of ordered triples $(r,m,p)$, where $n\equiv r \pmod{m}$ is a congruence in the covering and $p\in \P$ is the corresponding prime. Abusing notation slightly, we refer to $\C$ as a ``covering".
\section{Appending the Digits Only on the Right}\label{Section:OnlyRight}

Let $D=[d_1,d_2,\ldots, d_t]$, where $d_i\in \left\{0,1,2,\ldots ,9\right\}$.
Let $k$ be a positive integer, and suppose that $k=a_1a_2\cdots a_q$, where $a_i$ is the $i$th digit of $k$, reading from left to right. Then we construct the sequence of positive integers $\left\{s_n\right\}_{n=1}^{\infty}$ defined by
\[s_1=a_1a_2\cdots a_qd_1, \quad s_2=a_1a_2\cdots a_qd_1d_2, \quad s_3=a_1a_2\cdots a_qd_1d_2d_3, \quad\ldots \]
\[s_{t+1}=a_1a_2\cdots a_qd_1d_2 \cdots d_{t-1}d_td_1, \quad\ldots .\]
We need a covering $\{r_i \pmod{m_i}\}$ of the integers $n$, the indices of the sequence $\left\{s_n\right\}_{n=1}^{\infty}$, and a set of corresponding primes $\P$, such that $p_i\in \P$ divides $s_n$ when $n\equiv r_i\pmod{m_i}$.
In this situation, we require that the covering and the set of corresponding primes also satisfy the
 following conditions.
\begin{Con}\label{Conditions} Let $m_1\le m_2\le \cdots \le m_s$ be the moduli in the covering, and let $\P=\{p_1,p_2,\ldots ,p_s\}$ be a set of corresponding primes.
\begin{enumerate}
\item $m_i\equiv 0 \pmod{t}$ for all $i$.\label{Item:1}
\item No prime in $\P$ is a divisor of $10^t-1$.\label{Item:2}
\item The prime $p_i\in \P$ divides $10^{m_i}-1$.
\end{enumerate}
 \end{Con}

 \begin{remark}\label{Rem:MinMod}
 The minimum modulus in a covering satisfying Conditions \ref{Conditions} is at least $2t$.
\end{remark}
In the case of repeatedly appending the same digit to $k$ (i.e., when $t=1$), any covering satisfying Conditions \ref{Conditions} will vary slightly from the covering previously used by the first author \cite{L}. Nevertheless, both methods use the same single formula to describe the term $s_n$ in this case. However, the generalization presented here requires $t$ distinct formulas for $s_n$, one for each congruence class of $n$ modulo $t$. Item \ref{Item:1}. of Conditions \ref{Conditions} allows us to determine which of these formulas to invoke for a particular congruence in the covering, according to the congruence class of $r$ modulo $t$, where $n\equiv r \pmod{m}$ is a congruence in the covering. The most compact and useful way of writing our formulas for $s_n$ requires a division by $10^t-1$, and since $10^t-1$ is invertible modulo the corresponding prime $p\in \P$ by item \ref{Item:2}. in Conditions \ref{Conditions}, we are able to solve for $k$ modulo $p$. Finally, we use the Chinese remainder theorem to solve for $k$ in the resulting system of congruences. In Section \ref{Section:OnlyLeft} we will see that any covering used when appending $t$ digits on the right also works when appending $t$ digits on the left.
 We have been successful in achieving our goal for all $t\le 10$ when appending on a single side. Unfortunately, when $t>10$, certain computational roadblocks arise, which we discuss in Section \ref{Section:t larger than 10} and Section  \ref{Section: Final Remarks}.
 \subsection{The Cases $t\le 10$}\label{Section: t<=10}
  \begin{table}[h]
\caption{Right (or Left) $t\le 6$}
 \begin{center}
 \begin{tabular}{c|c}%\hline
 $t$ &  $\C$\\ \hline %\hline
 1&$\left\{(1,2,11),(0,3,37),(0,4,101),(4,6,7),(2,6,13)\right\}$ \\ \hline
 2&$\left\{(1,4,11),(3,4,101),(0,6,7),(2,6,13),(4,6,37)\right\}$ \\ \hline
 &$\left\{(1,6,7),(2,6,11),(3,6,13),(2,9,333667),(6,12,101),(4,12,9901),\right.$\\
 3&$(5,18,19),(17,18,52579),(0,24,73),(10,24,137),(22,24,99990001),$\\
 &$\left.(12,36,999999000001),(60,72,3169),(36,72,98641)\right\}$
 \\ \hline
 4& Given in Section \ref{Case:t=4R}\\ \hline
 5& Given in Section \ref{SubSectionL5}\\ \hline
&$\left\{ (1,12,101),(5,12,9901),(3,18,19),(15,18,333667),\right.$\\
&$(14,18,52579),(11,24,73),(19,24,137),(23,24,99990001),$\\
&$(22,30,31),(0,30,41),(12,30,211),(18,30,241),(4,30,271),$\\
&$(6,30,2906161),(24,30,9091),(16,30,2161),(8,36,999999000001),$\\
6&$(32,42,43),(20,42,127),(14,42,239),(2,42,10838689),$\\
&$(8,42,459691),(26,42,4649),(38,42,909091),(22,42,1933)$\\
&$(10,42,2689),(31,48,17),(7,48,9999999900000001),$\\
&$(45,48,5882353),(27, 54, 757),(9, 54, 440334654777631),$\\
&$(45, 54, 14175966169),(10, 54, 70541929),(58, 60, 61),$\\
&$\left.(40, 60, 39526741),(28, 60, 4188901),(10, 60, 27961)\right\}$\\ \hline
 \end{tabular}
 \end{center}
 \label{Table:1}
\end{table}

\begin{table}[h]
\caption{Right (or Left) $7\le t \le 10$}
  \begin{center}
 \begin{tabular}{c|ccc}%\hline
 $t$ & $|\C|$ & $M$ & $L$\\ \hline %\hline
 7 & 63 & 126 & 360360\\ \hline
8& 73 & 120 & 2882880\\ \hline
9& 80 & 144 & 6486480\\ \hline
10 & 80 & 140& 3603600\\ \hline
 \end{tabular}
 \end{center}
 \label{Table:2}
 \end{table}

 In Table \ref{Table:1} we give explicit coverings for values of $t\le 6$ that can be used in each of these cases, and to illustrate the techniques used to produce these coverings, we provide the details for the single case $t=4$ in Section \ref{Case:t=4R}. Because of the large number of congruences in $\C$ for values of $t$ with $7\le t\le 10$, Table \ref{Table:2} gives only the number of congruences in $\C$, denoted $|C|$, the largest modulus in $\C$, denoted $M$, and the least common multiple of the moduli in $\C$, denoted $L$, in these cases.

\subsubsection{A Detailed Example: The Case $t=4$}\label{Case:t=4R}
Let $D=[d_1,d_2,d_3,d_4]$.
Because we are appending four digits, the form of the term $s_n$ will vary according to the value of $n$ modulo 4. For example, when $n\equiv 1 \pmod{4}$, we have
\begin{align*}
  s_n&=10^nk+d_110^{n-1}+d_210^{n-2}+d_310^{n-3}+d_410^{n-4}+\\
  &\hspace*{.21in}\cdots +d_110^4+d_210^3+d_310^2+d_410+d_1\\
  &=10^nk+d_1\left(\frac{10^{n+3}-1}{10^4-1}\right)+\left(10^3d_2+10^2d_3+10d_4\right)\left(\frac{10^{n-1}-1}{10^4-1}\right).
\end{align*}



Therefore, when $n\equiv 0,1,2,3 \pmod{4}$, we have respectively:
\[s_n=\left\{\begin{array}{l}
10^nk+\left(10^3d_1+10^2d_2+10d_3+d_4\right)\left(\frac{10^n-1}{10^4-1}\right)\\
10^nk+d_1\left(\frac{10^{n+3}-1}{10^4-1}\right)+\left(10^3d_2+10^2d_3+10d_4\right)\left(\frac{10^{n-1}-1}{10^4-1}\right)\\
10^nk+\left(10d_1+d_2\right)\left(\frac{10^{n+2}-1}{10^4-1}\right)+\left(10^3d_3+10^2d_4\right)\left(\frac{10^{n-2}-1}{10^4-1}\right)\\
10^nk+\left(10^2d_1+10d_2+d_3\right)\left(\frac{10^{n+1}-1}{10^4-1}\right)+10^3d_4\left(\frac{10^{n-3}-1}{10^4-1}\right).\\
\end{array} \right.\]



  We use a table \cite{K} of prime factors of numbers of the form $10^m-1$ to construct, within the constraints of Conditions \ref{Conditions}, a list of possible moduli for our covering $\C$. We illustrate this procedure by determining the first few moduli in $\C$. According to Conditions \ref{Conditions}, the minimum modulus in $\C$ must be at least $2t=8$, each modulus must be divisible by 4, and we cannot use the primes 3, 11 and 101, since they divide $10^4-1$. Therefore, we start with $m_1=8$. There are two prime divisors of $10^8-1$ that do not divide $10^4-1$, namely 73 and 137. Thus, we can use the modulus 8 twice in our covering, with the corresponding primes 73 and 137. The next possible modulus in $\C$ is 12, which we can use four times since there are four prime divisors of $10^{12}-1$ available to us that we have not yet used: 7, 13, 37, 9901. The next possible modulus in $\C$ is 16. We can use it twice since there are two available primes divisors of $10^{16}-1$, namely 17 and 5882353.
 Continuing in this manner with consecutive multiples of 4, we eventually reach a list of moduli for which a covering actually exists (verified by Magma):
\[
\M=[8,8,12,12,12,12,16,16,20,20,20,20,20,24,28,28,28,28,28,28,32,32,32,32,32].
\] We can, in many cases, judiciously prune the list of moduli, and still construct a covering. For example, adding the modulus $28$ in the construction of $\M$ here increases the least common multiple of the moduli by a factor of 7. However, skipping over 28 and moving directly to 32 after 24 only increases the least common multiple of the moduli by a factor of 2, and therefore creates fewer ``holes" to fill. Consequently, we are able to construct a covering using the moduli in the list $\M$ without 28, and using one less 32. One advantage of this method is that it reduces the size of the smallest value of $k$ that we seek. In order to conserve space, we have attempted to employ such an optimizing strategy for our detailed examples, although such optimization is, in general, of no concern to us here.
One covering $\C$ generated by Magma is
\begin{align*}
\C=\left\{\right.& (1,8,73),(0,8,137),(2,12,7),(6,12,13),(10,12,37),(3,12,9901),(12,16,17),\\
& (5,16,5882353),(19,20,41),(11,20,271),(15,20,3541),(7,20,9091),(3,20,27961),\\
& (5,24,99990001),(20,32,353),(4,32,449),(29,32,641),(13,32,1409)\left.\right\}.
%& \left.\right\}.
\end{align*}
To illustrate the use of $\C$, we give a specific example.
\begin{example}
Suppose that $D=[1,3,5,7]$. We start with $(1,8,73)\in \C$. We want to find $k$ such that $s_n\equiv 0 \pmod{73}$. Since $n\equiv 1 \pmod{8}$, we have that $n\equiv 1 \pmod{4}$. Thus, we take the form for $s_n$ corresponding to $n\equiv 1 \pmod{4}$, set it equal to zero, and solve for $k$. Finally, we substitute in $n=1$ (since $n\equiv 1 \pmod{8}$), and reduce modulo 73 to get
\begin{align*}
k&=\frac{-d_1\left(\frac{10^{n+3}-1}{10^4-1}\right)-\left(10^3d_2+10^2d_3+10d_4\right)\left(\frac{10^{n-1}-1}{10^4-1}\right)}{10^n}\\
&\equiv 51 \pmod{73}, \quad \mbox{ when $n=1$}.\\
%&\equiv 2 \pmod{7}.
\end{align*}
For each element in $\C$, we get a corresponding congruence for $k$, and so we generate a system of congruences in $k$ modulo the primes from the ordered triples in $\C$. By the Chinese remainder theorem, the smallest positive solution to this system is \[k=329487380848404895573199266357097656655612892130353175.\]
\end{example}
%\subsubsection{The Cases $t\le 6$, $t\ne 4$}\label{Section: t<=6}

\subsection{The Cases $t\ge 11$}\label{Section:t larger than 10}
The minimum modulus in any covering $\C$ here is at least $2t$, and so Remark \ref{Rem:Covering necessity} tells us that the largest modulus in $\C$ must grow accordingly. There are then two implications. The first implication is that for large $t$, we will eventually run out of prime factors of $10^m-1$ in our database. The second implication is that, even if we do have the prime factors of $10^m-1$ in our database, the number of moduli needed to construct a covering is growing so rapidly that we very quickly reach a point in which the Magma program runs out of memory before it can generate a covering. Although, theoretically, we see no obstruction to the existence of a covering satisfying Conditions \ref{Conditions} when $t\ge 11$, we are unable to prove or disprove the existence of such a covering. For more discussion, see Section \ref{Section: Final Remarks}.

\section{Appending the Digits Only on the Left}\label{Section:OnlyLeft}

Again we let $D=[d_1,d_2,\ldots, d_t]$, where $d_i\in \left\{0,1,2,\ldots ,9\right\}$. Let $k$ be a positive integer, and suppose that $k=a_1a_2\cdots a_q$, where $a_i$ is the $i$th digit of $k$, reading from left to right. Then we construct the sequence of positive integers $\left\{s_n\right\}_{n=1}^{\infty}$ defined by
\[s_1=d_1a_1a_2\cdots a_q, \quad s_2=d_2d_1a_1a_2\cdots a_q, \quad s_3=d_3d_2d_1a_1a_2\cdots a_q, \quad\ldots \]
\[s_{t+1}=d_1d_td_{t-1}\cdots d_2d_1a_1a_2 \cdots a_q, \quad\ldots .\]
As before, we wish to determine values of $k$ such that $s_n$ is composite for all $n\ge 1$. However, because we are appending the digits on the left, there are two minor complications that arise. First, each of the expressions for $s_n$ now involves $q$, the number of digits of $k$. Second, assuming we can solve the system of congruences for $k$ that is produced by our methods, we would like to ensure that there is a solution $k$ that is not divisible by 2 or 5, since such values of $k$ constitute a trivial situation. Fortunately, we can overcome both of these concerns. We illustrate how to deal with these complications in the case when $t=5$. Despite these complications, we see that, as in the situation when we were appending the digits on the left of $k$, the number of distinct formulas for $s_n$ required here is $n$, one for each congruence class modulo $n$. Therefore, since the coverings we seek must satisfy Conditions \ref{Conditions}, the same covering can be used for a particular $t$, regardless of whether we are appending the digits on the left or right of $k$. See Tables \ref{Table:1} and \ref{Table:2}.
\subsection{A Detailed Example: The Case $t=5$}\label{SubSectionL5}
Let $D=[d_1,d_2,d_3,d_4,d_5]$.
We begin by formulating the term $s_n$. As before,
we see here that the form of $s_n$ is dependent on the congruence class of $n$ modulo the number of elements in our list $D$, which in this example is $5$. But here, $s_n$ is also a function of $q$, the number of digits in $k$.  When $n\equiv 0,1,2,3,4 \pmod{5}$, we have respectively:\\ %. Thus, when $n\equiv 0,1,2,3,4 \pmod{5}$, we have respectively\\

\[s_n=\left\{\begin{array}{l}
k+\left(10^qd_1+10^{q+1}d_2+10^{q+2}d_3+10^{q+3}d_4+10^{q+4}d_5\right)\left(\frac{10^n-1}{10^5-1}\right)\\\\
k+10^qd_1\left(\frac{10^{n+4}-1}{10^5-1}\right)\\
\quad\quad+\left(10^{q+1}d_2+10^{q+2}d_3+10^{q+3}d_4+10^{q+4}d_5\right)\left(\frac{10^{n-1}-1}{10^5-1}\right)\\\\
k+\left(10^qd_1+10^{q+1}d_2\right)\left(\frac{10^{n+3}-1}{10^5-1}\right)\\
\quad\quad+\left(10^{q+2}d_3+10^{q+3}d_4+10^{q+4}d_5\right)\left(\frac{10^{n-2}-1}{10^5-1}\right)\\\\
k+\left(10^qd_1+10^{q+1}d_2+10^{q+2}d_3\right)\left(\frac{10^{n+2}-1}{10^5-1}\right)\\
\quad\quad+\left(10^{q+3}d_4+10^{q+4}d_5\right)\left(\frac{10^{n-3}-1}{10^5-1}\right)\\\\
k+\left(10^qd_1+10^{q+1}d_2+10^{q+2}d_3+10^{q+3}d_4\right)\left(\frac{10^{n+1}-1}{10^5-1}\right)\\
\quad\quad+10^{q+4}d_5\left(\frac{10^{n-4}-1}{10^5-1}\right).\\\\
\end{array} \right.\]

Here we wish to construct a covering and a set of corresponding primes $\P$ that satisfy Conditions \ref{Conditions} with $t=5$. We proceed, as in Section \ref{Section:OnlyRight}, to construct the covering
\begin{align*}
\C=\left\{\right.& (0,10,11),(5,10,9091),(13,15,31),(2,15,37),(7,15,2906161),(6,20,101),\\
& (14,20,3541),(19,20,27961),(12,30,7),(18,30,13),(1,30,211),(11,30,241),\\
& (3,30,2161),(4,40,73),(29,40,137),(16,40,1676321),(36,40,5964848081),\\
& (8,45,238681),(23,45,333667),(38,45,4185502830133110721),(57,60,61),\\
& (27,60,9901),(51,60,4188901),(21,60,39526741),(9,80,17),\\
& (49,80,5070721),(24,80,5882353),\\
& (64,80,19721061166646717498359681)\left.\right\}.
\end{align*}

As in Section \ref{Section:OnlyRight}, each of the elements in $\C$ corresponds to a particular congruence in a system of congruences for $k$. To avoid the trivial situations that $k$ is divisible by 2 or 5 when we solve the system, we add to the system the additional congruence $k\equiv d \pmod{10}$, where $d\in \{1,3,7,9\}$. We must still contend with the fact that each of the other congruences in the system is dependent on $q$, the number of digits of $k$. However, this problem is easily rectified. We introduce some notation. We let $\ell=10 \prod_{p_i\in \P}p_i$, the least common multiple of the moduli in our system of congruences for $k$, and we let $\delta(z)$ denote the number of digits in the positive integer $z$. For any positive integer $w$, we let $v_w=\delta(\ell)+w$. For any value of $w$, we can substitute $v_w$ in for $q$ into each of the congruences in the system. This allows us to solve for $k$ using the Chinese remainder theorem. If $k_0$ is the smallest positive integer solution to this system, then all solutions to the system satisfy the congruence $x\equiv k_0 \pmod{\ell}$. Note that the number of digits in $k_0$ is at most $\delta(\ell)$. It is then easy to see that there is a positive integer $a$ such that $\delta(k_0+a  \ell)=v_w$. In other words, $k_0+a \ell$ is a solution to our system with exactly $q$ digits, and since $w$ can be any positive integer, we get infinitely many such solutions. To illustrate these ideas and the use of $\C$, we give an example.
\begin{example}\label{Ex:Left}
Suppose that $D=[3,7,2,5,4]$. We wish to find $k$ such that $s_n\equiv 0 \pmod{p}$ for all $p \in \P$.  For each ordered triple $(r,m,p)$ in $\C$, we substitute $r$ in for $n$ into the formula for $s_n$, where $n\equiv r \pmod{5}$. Then we set each of these expressions equal to zero, and solve for $k$. Here we have that $\delta(\ell)=146$, and we choose to let $q=147$. We reduce each of the congruences modulo the corresponding prime $p\in \P$, and we add the additional congruence $k\equiv 1 \pmod{10}$ to avoid certain trivial situations.
By the Chinese remainder theorem, the smallest positive solution to this system is
\begin{center}%\vspace{1pc}
{\normalsize $k_0$=10982121324843319893051990697602742531038520281080212527033380031702058677\\429664543284836432559714302725330265818303246372107452182645651819050681.}
\end{center}
However, $\delta(k_0)=146$, and so we must add a multiple of $\ell$ to $k_0$ to get an integer that has exactly 147 digits, which will then be a solution to our problem. The least value of $a$ such that $\delta(k_0+a\ell)=147$ is $a=9$. Thus, the smallest solution produced by our methods is
 \begin{center}%\vspace{1pc}
{\normalsize $k$=110983121334843519896052020698002747531098520881087212607034180039702148678\\329672543364837232566714362725930270818343246672110452202645751820050691.}
\end{center}
\end{example}

\begin{remark}
 We should mention that of course the same computational obstacles for larger values of $t$ that we faced in Section \ref{Section:OnlyRight} also plague us here.
\end{remark}

\section{Appending the Digits in an Alternating Manner}
\label{Section:Alternating}
Let $D=[d_1,d_2,\ldots, d_t]$, where $d_i\in \left\{0,1,\ldots ,9\right\}$. Let $k$ be a positive integer, and suppose that $k=a_1a_2\cdots a_q$, where $a_i$ is the $i$th digit of $k$, reading from left to right. By first starting on the right and appending the elements of list $D$ in an alternating manner, we construct the sequence of positive integers $\left\{s_n\right\}_{n=1}^{\infty}$ defined by
\[s_1=a_1a_2\cdots a_qd_1, \quad s_2=d_2a_1a_2\cdots a_qd_1, \quad s_3=d_2a_1a_2\cdots a_qd_1d_3, \quad\ldots \]
As before, we wish to determine values of $k$ such that $s_n$ is composite for all $n\ge 1$. The methods we use here are similar to the methods used in the previous sections, and they are valid regardless of whether we start appending on the left or on the right of $k$. Only the formulas for $s_n$ will be affected. In either situation, we require ${\rm lcm}(2,t)$ versions of $s_n$, which implies that we have two subcases: $t$ even and $t$ odd. Accordingly, we alter Conditions \ref{Conditions} as follows.
\begin{Con}\label{ConditionsA} Let $m_1\le m_2\le \cdots \le m_s$ be the moduli in the covering, and let $\P=\{p_1,p_2,\ldots ,p_s\}$ be a set of corresponding primes. Let $a={\rm lcm}(2,t)/2$ and $b={\rm lcm}(2,t)$.
\begin{enumerate}
\item $m_i\equiv 0 \pmod{b}$ for all $i$.\label{Item:1A}
\item No prime in $\P$ is a divisor of $10^a-1$.\label{Item:2A}
\item The prime $p_i\in \P$ divides $10^{m_i/2}-1$.
\end{enumerate}
 \end{Con}
 The variances in Conditions \ref{ConditionsA} from Conditions \ref{Conditions} are due to the period of occurrence of $d_i \in D$ on either side of $k$, and the number of variations of $s_n$. Note that Conditions \ref{ConditionsA} imply that the minimum modulus in $\C$ must be at least $2t$ when $t$ is even, and at least $4t$ when $t$ is odd. One additional implication that follows from Conditions \ref{ConditionsA} is that if we are able to find a covering and a set of corresponding primes satisfying Conditions \ref{ConditionsA} for some particular odd value of $t$, then the same covering and set of primes can be used for the case of $2t$. In the alternating situation when $t\ge 7$ is odd, we are faced with the same computational difficulties that we encountered when appending on a single side in the cases $t\ge 11$. These obstructions are discussed in Section \ref{Section:t larger than 10}. To illustrate the general methods used in the alternating situation, we give a detailed analysis of the case $t=4$ in Section \ref{Section: t=4A}.

\subsection{The Cases $t\le 10$}\label{Section: t<=10A}
 Although an explicit covering is given only in the case of $t=4$ in Section \ref{Section: t=4A}, we give, as we gave in Section \ref{Section: t<=10} in the situation of appending on a single side, some basic information in all other cases when $t\le 10$, except $t=7$ and $t=9$. This general information is given in Table \ref{Table:3}, where $|C|$ is the number of congruences in the covering $\C$, $M$ is the largest modulus in $\C$, and $L$ is the least common multiple of the moduli in $\C$.

\begin{table}[ht]
 \caption{Alternating $t\le 10$}
 \begin{center}
 \begin{tabular}{c|ccc}%\hline
 $t$ & $|\C|$ & $M$ & $L$\\ \hline %\hline
1 & 31 & 84 & 840\\ \hline
2& \multicolumn{3}{c}{Same as $t=1$}\\ \hline
3& 79 & 420 & 15120\\ \hline
 4&  \multicolumn{3}{c}{Given in Section \ref{Section: t=4A}}\\ \hline
%4 & 43 & 168 & 3360\\ \hline
5 & 331 & 15840 & 7207200\\ \hline
6 & \multicolumn{3}{c}{Same as $t=3$}\\ \hline
7& \multicolumn{3}{c}{Unknown}\\ \hline
8 & 177 & 1584 & 221760\\ \hline
9& \multicolumn{3}{c}{Unknown}\\ \hline
10 & \multicolumn{3}{c}{Same as $t=5$}\\ \hline
\end{tabular}
\end{center}
 \label{Table:3}
 \end{table}


\subsubsection{A Detailed Example: The Case $t=4$}\label{Section: t=4A}
We give the ${\rm lcm}(2,t)=4$ formulas for $s_n$ for the situation when we start appending on the right. The formulas for $s_n$, and the methods used, when we start appending on the left are similar. When $n\equiv 0,1,2,3 \pmod{4}$, we have respectively:\\

\[s_n=\left\{\begin{array}{l}
10^{n/2}k+\left(10d_1+10^{(n/2)+q}d_2+d_3+10^{(n+2)/2+q}d_4\right)\left(\frac{10^{n/2}-1}{10^2-1}\right)\\\\
10^{(n+1)/2}k + d_1\left(\frac{10^{(n+3)/2}-1}{10^2-1}\right)\\
\quad\quad+\left(10^{(n+1)/2+q}d_2+10d_3+10^{(n+3)/2+q}d_4\right)\left(\frac{10^{(n-1)/2}-1}{10^2-1}\right)\\\\
10^{n/2}k+\left(10d_3+10^{(n+2)/2+q}d_4\right)\left(\frac{10^{(n-2)/2}-1}{10^2-1}\right)\\
\quad\quad+\left(d_1+10^{(n/2)+q}d_2\right)\left(\frac{10^{(n+2)/2}-1}{10^2-1}\right)\\\\
10^{(n+1)/2}k+10^{(n+3)/2+q}d_4\left(\frac{10^{(n-3)/2}-1}{10^2-1}\right)\\
\quad\quad+ \left(10d_1+10^{(n+1)/2+q}d_2+d_3\right)\left(\frac{10^{(n+1)/2}-1}{10^2-1}\right).\\\\
\end{array} \right.\]
The covering we use here is
\begin{align*}
\C=\left\{\right.& (1, 8, 101),(2, 12, 7),(10, 12, 13),(6, 12, 37),(13, 16, 73),(3, 16, 137),\\
& (8, 20, 41), (4, 20, 271), (16, 20, 9091), (15, 24, 9901), (23, 28, 239),\\
& (7, 28, 4649), (11, 28, 909091), (5, 32, 17), (21, 32, 5882353), (0, 40, 27961),\\
& (12, 40, 3541), (31, 44, 23), (39, 44, 513239), (23, 44, 21649), (27, 44, 8779),\\
& (35, 44, 4093), (15, 56, 29), (31, 56, 281), (12, 60, 31), (32, 60, 211),\\
& (20, 60, 241), (40, 60, 2906161), (52, 60, 2161), (11, 64, 353), (27, 64, 449),\\
& (43, 64, 641), (59, 64, 1409), (31, 64, 69857), (60, 80, 5964848081), (20, 80, 1676321),\\
& (47, 84, 43),(83, 84, 127), (55, 84, 1933), (19, 84, 2689) \left.\right\}.
\end{align*}

\begin{example}
Suppose that $D=[7,1,4,9]$. We follow the methods used in Section \ref{SubSectionL5}. Here $\delta(\ell)=131$, and we choose $v=132$. Then the smallest value of $k$ with 132 digits produced by this process, such that every term of the sequence $\left\{s_n\right\}_{n=1}^{\infty}$ is composite, is
\begin{center}
{\normalsize $k$=13096455548520391404136872903624576303901893826181040740105459909726\\1712572158731534146652935794771514600650784321669697928418283852.}
\end{center}
\end{example}




\section{Final Remarks}\label{Section: Final Remarks}

As mentioned in Section \ref{Section:t larger than 10}, there are certain computational restrictions that prohibit us from extending the results in Theorem \ref{Thm:Main} to larger values of $t$. Theoretically, however, it might be possible to prove the existence of a covering satisfying Conditions \ref{Conditions} or Conditions \ref{ConditionsA}, which in turn, would prove the existence of the desired values of $k$. 

One possible approach is the following. Although we might not know the explicit prime divisors of numbers of the form $10^m-1$, there are theorems \cite{Bang, BV, S, Z} that guarantee the existence of certain prime divisors of such numbers. For every modulus $m$ in the covering, these theorems guarantee the existence of at least one prime divisor of $10^m-1$ that does not divide $10^n-1$ for any integer $n<m$. For certain values of $m$, one of these theorems \cite{S} guarantees the existence of two such prime divisors. We can then use these theorems to increase the number of available primes by examining the divisors $d$ of the moduli to determine which prime divisors of $10^d-1$ we have not yet used in $\P$. In other words, it is conceivable that certain moduli can be repeated in the covering. From our experience, it seems that, in general, this procedure is inadequate to generate a desired covering, although we cannot prove it.

A second possible approach is to assume that a famous conjecture of Erd\H{o}s is true. His conjecture is that, for every positive integer $m$, there exists a covering with minimum modulus $m$, such that all moduli are distinct and odd. If we could deduce from the truth of this conjecture that, for any positive integer $m$, a covering exists with minimum modulus $m$, such that the moduli are distinct and are all divisible by $t$, then this result, combined with the existence theorems above, would imply the existence of a covering satisfying Conditions \ref{Conditions} or Conditions \ref{ConditionsA}. However, such a fact does not seem to follow from the conjecture of Erd\H{o}s, and the current thinking \cite{N} is that the conjecture of Erd\H{o}s might very well be false.


\section{Acknowledgments}
The authors thank the referee for the many valuable suggestions. The authors also thank Carl Pomerance for comments concerning the discussion in Section \ref{Section: Final Remarks}.


\begin{thebibliography}{10}
\bibitem{Bang} A. S. Bang, Taltheoretiske Unders\S{o}gelser,
\emph{Tidsskrift for Mat.} \textbf{5(4)} (1886), 70--80, 130--137.

\bibitem{BV} G. D. Birkhoff and H. S. Vandiver, On the integral
divisors of $a^n - b^n$, \emph{Ann. of Math.}
\textbf{5} (1903--1904), 173--180.

\bibitem{BC} W. Bosma and J. Cannon, eds., 
{\it Discovering Mathematics with Magma: Reducing the Abstract to the Concrete},
Algorithms and Computations in Mathematics, Vol.\ 19, Springer, 2006.

\bibitem{E} P. Erd\H{o}s, On integers of the form $2\sp k+p$ and some related problems, \emph{Summa Brasil. Math.} \textbf{2}  (1950), 113--123.

\bibitem{L} L. Jones, When does appending the same digit repeatedly on
the right of a positive integer generate a sequence of composite
integers?, \emph{Amer. Math. Monthly}, \textbf{118} (2011), 153--160.

\bibitem{MK} M. Kamada, Factorizations of $11\cdots11$
(Repunit), available electronically at
\url{http://homepage2.nifty.com/m_kamada/math/11111.htm}.

\bibitem{K} Y. Koide, Factors of repunit numbers,
available electronically at
\url{http://www.h4.dion.ne.jp/~rep}.

\bibitem{N} P. Nielsen, A covering system whose
 smallest modulus is 40, \emph{J. Number Theory}, \textbf{129} (2008),
640--666.

\bibitem{S} A. Schinzel, On primitive prime factors of
$a\sp{n}-b\sp{n}$, \emph{Proc. Cambridge Philos. Soc.} \textbf{58}
(1962), 555--562.

\bibitem{Z} K. Zsigmondy, Zur Theorie der Potenzreste,
\emph{Monatshefte f\"{u}r Math. u. Phys.} \textbf{3} (1892), 265--284.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B99; Secondary 11A51, 11A07, 11A41, 11-04.

\noindent \emph{Keywords: } covering, composite number.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 1 2011;
revised version received January 24 2011; May 3 2011. 
Published in {\it Journal of Integer Sequences}, May 4 2011.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                



.
