<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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{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 
Prime and Composite Terms in Sloane's \\
\vskip .1in
Sequence A056542}
\vskip 1cm
\large
Tom M\"uller\\
Institute for Cusanus-Research\\
University and Theological Faculty of Trier\\
Domfreihof 3 \\
54290 Trier \\
Germany\\
\href{mailto:muel4503@uni-trier.de}{\tt muel4503@uni-trier.de} \\
\end{center}

\vskip .2 in
\begin{abstract}
We give
the complete factorization of the first fifty terms of the sequence
$a_n:=na_{n-1}+1$ with $a_1:=0$.  We searched the terms $a_n$ 
for primes up to $n=1019$ with the result that only the
indexes 4, 8, 18, 20 and 70 provide primes. A final section deals with
some conjectures on prime terms in this sequence.
\end{abstract}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


% \documentclass[11pt,a4paper]{article}

% \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb}

\section{Introduction}
Consider the sequence of integers defined by $a_n:=na_{n-1}+1$
with $a_1:=0$. This sequence is \seqnum{A056542} in Neil Sloane's Online
Encyclopedia of Integer Sequences~\cite{sloane}.
In this paper we give the complete factorization of the first
fifty terms and deal with the question what terms are prime numbers for
$n&lt;1020$. To do this we need two equivalent expressions for the terms
$a_n$. 

Using a simple induction argument we can show that
\begin{eqnarray}\label{one}
a_n=\sum_{\nu=2}^n\frac{n!}{\nu!}.
\end{eqnarray}

     The study of the convergence of the exponential series 
(which is, among other things, used to prove the irrationality of $e$)
allows us moreover to write
\begin{eqnarray}\label{two}
a_n=\lfloor n! (e-2)\rfloor = \lfloor n!e\rfloor -2n!.
\end{eqnarray}
Using the first expression it is easy
to prove a criterion for the compositeness of certain terms.

\section{Composite terms}

From the definition of the sequence it follows immediately that for odd
$n&gt;1$ the term $a_n$ is even and greater than $3$ and hence composite.
So only even indexes can provide potential prime numbers. Expression
(\ref{one}) implies the following result.

\newtheorem{theorem1}{Theorem}[section]
\begin{theorem1}
Let $p$ be a prime number and $n$ be a natural number with $p\leq n$. If $p$ is a divisor of $a_n$ then $p$ divides $a_{n+p}$ as well.
\end{theorem1}
Proof: Writing 
\begin{eqnarray}\label{exp1}
a_{n+p}=
\sum_{\nu=2}^{p-1}\frac{(n+p)!}{\nu!}+\sum_{\nu=p}^{n+p}\frac{(n+p)!}{\nu!},
\end{eqnarray}
we see that the first sum on the right side contains the factor $p$. Concerning the second sum, we obtain (e.g., by induction on $n$)

\begin{eqnarray}\label{exp2}
\sum_{\nu=p}^{n+p}\frac{(n+p)!}{\nu!}=
\left( \sum_{\nu=0}^n \frac{n!}{\nu!} \right) +pk
\end{eqnarray}
where $k$ is a natural number. This is equivalent to
\begin{eqnarray*}
a_{n+p}=a_n+2n!+pK
\end{eqnarray*}
with another natural number
$K$ absorbing $k$ and the respective factor of the first sum in (\ref{exp1}).
Hence $a_{n+p}$ is a multiple of $p$ if $a_n$ is. \hfill $\square$\\ 

One consequence of the theorem is the fact that for a given prime $p$
it is enough to search among the terms $a_p,a_{p+1},\ldots,a_{2p-1}$
for multiples of $p$. Numerical computations lead to the results
presented in Table \ref{tab1}.

\begin{table}[ht]\begin{center}
\begin{tabular}{|l l| l l |}\hline
$p$ &amp; $n$ with $p|a_n$ &amp; $p$ &amp; $n$ with $p|a_n$ \\ \hline\hline
 2 &amp; 3		&amp; 113 &amp; 163\\	
 5 &amp; 7, 9       &amp; 127 &amp; 135\\
13 &amp; 17, 23, 25 &amp; 131 &amp; 153, 164\\
19 &amp; 25, 33     &amp; 137 &amp; 144, 153\\
23 &amp; 37, 41     &amp; 149 &amp; 218\\
29 &amp; 52		&amp; 163 &amp; 168\\
31 &amp; 45, 50	&amp; 167 &amp; 242\\
37 &amp; 53, 71, 73 &amp; 173 &amp; 336\\
41 &amp; 78		&amp; 179 &amp; 351\\
43 &amp; 62		&amp; 181 &amp; 276\\
59 &amp; 100	&amp; 193 &amp; 250, 255\\
71 &amp; 81, 120	&amp; 197 &amp; 228, 297\\
83 &amp; 157	&amp; 211 &amp; 269, 357, 391, 415\\
97 &amp; 123	&amp; 223 &amp; 363\\
103 &amp; 109	&amp; 227 &amp; 411, 436\\
107 &amp; 158	&amp; 239 &amp; 418\\
109 &amp; 196, 213	&amp; 251 &amp; 279\\ \hline
\end{tabular}
\caption{Prime numbers $p$ dividing the term $a_n$}\label{tab1}
\end{center}\end{table}

Furthermore, we can now use the theorem to sift the prime candidates and retain more than half of them as composites.
The $a_n$'s that could not be identified being the product of two
nontrivial factors with our sieve method were tested for compositeness
by trying to find a small factor with a standard factorization
algorithm, which again eliminated about half the terms.  Each remaining
term was subjected to the Fermat test

\begin{eqnarray}\label{fermat}
2^{a_n-1} \equiv 1 \bmod a_{n}.
\end{eqnarray}
It turned out that in all the cases, exept for $n\in\{4,8,18,20,70\}$,
the congruence failed,
and hence the respective $a_n$ was composite.
We studied the indexes $n&lt;1020$.
Testing one term took an average CPU time of about one hour.

\section{Prime terms}
In the previous section we pointed out that only the terms
\begin{eqnarray*}
a_4 &amp; = &amp; 17\\
a_8 &amp; = &amp; 28961\\
a_{18} &amp; = &amp; 4598708691828421\\
a_{20} &amp; = &amp; 1747509302894800001\\
a_{70} &amp; = &amp; \hbox{\tiny 8603990361433692835766763032506384134769654780784715495311087517908153547994512075361554378508046501}
\end{eqnarray*}
remain potential prime numbers. For $n=4,8,18,20$ it is simple to prove
their primality, for example by trial division up to the respective
square roots. For $a_{70}$, which is a 100-digit number, primality can
be established using two theorems of Brillhart, 
Lehmer and  Selfridge~\cite{brillhart}.

%\newtheorem{theorem}{Theorem}[section]

\begin{theorem}\label{brill1}
Let $N-1 = \prod p_i^{\alpha_i}$ be the complete factorization of the
integer $N-1$. If for each prime factor $p_i$ there exists an
$a_i$ such that $N$ fulfills $a_i^{N-1}\equiv 1$ (mod $N$), but
$a_i^{(N-1)/p_i}\not\equiv 1$ (mod $N$), then $N$ is prime.

\end{theorem}
\newtheorem{theorem2}[theorem]{Theorem}
\begin{theorem2}\label{brill2}
Let $N+1 = \prod p_i^{\alpha_i}$ be the complete factorization of the integer
$N+1$.
Let $\mathcal{U}$ be the set of Lucas sequences $\{U_k^{(i)}\}$ 
with the given discriminant $D$ for which the Jacobi symbol $(D/N)=-1$.
If for each $p_i$ there exists a Lucas sequence in
$\mathcal{U}$ such that $N$ is a divisor of $U_{N+1}^{(i)}$,
but not a divisor of $U_{(N+1)/p_i}^{(i)}$, then $N$ is prime.
\end{theorem2}

\paragraph{Remark:} Let $P$ and $Q$ be integers with the discriminant
$D:=p^2-4Q\not=0$. Then the Lucas sequences are defined recursively by
\begin{eqnarray}\label{lucas1} U_{k+2} = PU_{k+1}-QU_{k}, \qquad k\geq
0, \quad U_0=0, \quad U_1=1,
\end{eqnarray}
and
\begin{eqnarray}\label{lucas2}
V_{k+2} = PV_{k+1}-QV_{k}, \qquad k\geq 0, \quad V_0=2, \quad V_1=P.
\end{eqnarray}
A simple method to compute large terms of a given Lucas sequence is
presented in the paper of Brillhart et al.
(\cite[pp.\ 627--628]{brillhart}) as well.

With this we can settle the primality of $a_{70}$.
\newtheorem{theo3}[theorem]{Theorem}
\begin{theo3}
The number $a_{70}$ is prime.
\end{theo3}
Proof: We have
$$a_{70}+1=2\cdot 3 \cdot 11 \cdot 471193 \cdot p_{93},$$
where
\begin{eqnarray*}
p_{93} &amp; = &amp; \hbox{\tiny 276666865434658243552094076373979681579672293479713404939810982616341330249301822966628239979}
\end{eqnarray*}
is a 93-digit probable prime. If we assume that $p_{93}$ is prime, the
claim follows with theorem \ref{brill2} by setting $D=-3$. Then the
divisibility criteria hold for the factor 2 with $P=Q=1$, for the
factor 3 with $P=Q=3$ and for the other three factors with $P=5$ and
$Q=7$.

So, we need the primality of $p_{93}$. To reach this goal, we
consider the factorization $$p_{93}-1=2\cdot 3\cdot 167\cdot 263 \cdot
457 \cdot 8377 \cdot p_{81}$$ with a 81-digit probable prime
\begin{eqnarray*} p_{81} &amp; = &amp; \hbox{\tiny 
274238840573141405175902476234412618955309935656050257207045603051300234586527927.}  \end{eqnarray*}
Again, if we assume that $p_{81}$ is prime the primality of $p_{93}$
follows with $a_i=3$ for all $i=1,\ldots,7$ in theorem \ref{brill1}.

The next step consists in proving the primality of $p_{81}$. For this,
we apply theorem \ref{brill1} again with the base $a_i=3$ to
\begin{eqnarray*} p_{81}-1 = 2 \cdot q_{81} \end{eqnarray*} where
\begin{eqnarray*} q_{81} &amp; = &amp; \hbox{\tiny 
137119420286570702587951238117206309477654967828025128603522801525650117293263963} \end{eqnarray*}
is another 81-digit probable prime. A final step shows the primality of
$q_{81}$. This follows with theorem \ref{brill2} and \begin{eqnarray*}
q_{81} + 1 &amp; = &amp; 2^2 \cdot 3 \cdot 13 \cdot 29 \cdot 4793 \cdot 15227
\cdot 20422008121 \cdot\\ &amp; &amp; \cdot 688270315985433959 \cdot
28276698587131486301 \cdot \\ &amp; &amp; \cdot 1044884793638901916109.
\end{eqnarray*} These final factors are small enough to be easily
proved prime. Here again a discriminant $D=-3$ gives the wanted results
with $P=5$ and $Q=7$ for all ten prime factors. \hfill $\square$\\

The results of this section are summarized in Sloane's OEIS
A070213~\cite{sloane}.\ \paragraph{Remark:} The sequence can be
generalized to $b_n:=nb_{n-1}+1$ by defining another initial term
$b_1:=b\in\mathbb{N}$. Then we can establish the relation
\begin{eqnarray*} b_n=bn!+a_n.  \end{eqnarray*} Therefore the sieve
method will work for the generalized case too. How many primes are
there in the respective sequences?\\

\section{Complete factorization of the first fifty terms}
The following factorization results were obtained using Lenstra's elliptic curve
method~\cite{lenstra}. The factors found were
furthermore tested for their primality again using trial division up to
the square root. All computations in this sections were realized in
almost 100 hours of CPU time on two Pentium-I computers. The results
can be found in Tables \ref{fac1} and \ref{fac2}.

\section{Conclusions and conjectures}
Using a heuristic argument similar to those used, e.g., by Hardy
and Wright (\cite[p.\ 15]{hardy}) for Fermat numbers, or by 
Wagstaff~\cite{wagstaff} for Mersenne numbers, we can formulate
some conjectures about the
asymptotic behavior of prime numbers in sequence A056542.

In order to do this, we extended Table \ref{tab1} up to the first
$10,000$ primes by steps of 1000 primes, noting only the number $N(p)$
of $n$ in the interval $1&lt;n&lt;p$, resp. $p\leq n &lt;2p-1$, for which $p$
divides $a_n$ and computed the averages $$\sigma(x)=\frac{\sum_{p\leq
x}N(p)}{2\pi(x)}$$ with these data. Here
$\pi(x)=\#\{p\in\mathbb{P}:p\leq x\}$ denotes the prime number counting
function.

These results, which are given in Table \ref{tab5}, suggest that the average number of such $n$ taken over all primes $p$ less than a given $x$ is approximately equal to $1$, which might indicate that $\sigma(x)\rightarrow 1$ for $x\rightarrow \infty$.
\begin{table}[ht]\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\hline
$\pi(x)=$	&amp; 	1000	&amp;	2000	&amp;	3000	&amp;	4000	&amp;	5000\\\hline
$1&lt;n&lt;p$		&amp;	1.019	&amp;	1.024	&amp;	1.006	&amp;	1.005	&amp;	1.000\\
$p\leq n &lt;2p$	&amp;	0.973	&amp;	1.001	&amp;	1.005	&amp;	1.003	&amp;	1.010\\
$\sigma(x)=$	&amp;	0.996	&amp;	1.013	&amp;	1.006	&amp;	1.004	&amp;	1.005\\\hline
$\pi(x)=$	&amp;	6000	&amp;	7000	&amp;	8000	&amp;	9000	&amp;	10000\\\hline
$1&lt;n&lt;p$		&amp;	0.998	&amp;	0.998	&amp;	0.990	&amp;	0.994	&amp;	0.986\\
$p\leq n &lt;2p$	&amp;	1.004	&amp;	1.004	&amp;	1.008	&amp;	1.005	&amp;	0.999\\
$\sigma(x)=$	&amp;	1.001	&amp;	1.001	&amp;	0.999	&amp;	1.000	&amp;	0.993\\\hline
\end{tabular}\caption{The averages of terms $a_n$ that are divides by primes $p$ (rounded)}\label{tab5}
\end{center}\end{table}\\

If we assume that this is the case, this would say that, on average, a
prime $p$ divides $a_n$ (for large $n$) with probability $\frac{1}{p}$.
But this would mean that the terms of our sequence behave just like
``typical" numbers of the same size, and hence are just as likely to be
prime.  So, according to the famous Prime Number Theorem, the
probability for any given $a_n$ to be prime, would be
$\frac{1}{\ln(a_n)}$. Applying the well known Stirling formula to
expression (\ref{two}), we get $$\ln(a_n)\approx\ln(n!)\approx A \cdot
n\ln(n)$$ with a constant $A&lt;1$. If this all is true, there are two
consequences worth mentioning. On the one hand, the number $P(x)$ of
prime terms $a_n$ with indices $n\leq x$ would be
\begin{eqnarray}\label{asymp} P(x)\approx A^{-1}\sum_{n=2}^{\lfloor x
\rfloor} \frac{1}{n\ln(n)}.  \end{eqnarray}

Hence, as the series in
(\ref{asymp}) diverges for $x\rightarrow\infty$, there would be
infinitely many prime terms in sequence A056542.

On the other hand,
having a glance at the known prime terms suggests that $A^{-1}\approx
2.3$. Using this parameter, solving the equation $P(x)=6$ would predict
a sixth prime term for an index $n\approx 780$. A seventh prime term is
expected to accure with the index $n\approx 33700$. So, there should be
a sixth prime in the interval $1020\leq n&lt; 33700$ (and more likely it
should be found short after the index 1020), if we guessed right.
Nevertheless, prime terms $a_n$ look like being very rare after all.

\begin{table}[ht]\begin{center}
\begin{tabular}{| l l |}\hline
$n$ &amp; factor($a_n$)\\ \hline \hline
2   &amp; 1\\
3   &amp; $2^2$\\
4   &amp; 17\\
5   &amp; $2 \cdot 43$\\
6   &amp; $11\cdot 47$\\
7   &amp; $2^2\cdot 5\cdot 181$\\
8   &amp; 28961\\
9   &amp; $2\cdot 5^2\cdot 13\cdot 401$\\
10  &amp; $67\cdot 38903$\\
11  &amp; $2^3\cdot 3583939$\\
12  &amp; $5\cdot 68811629$\\
13  &amp; $2\cdot 2236377943$\\
14  &amp; $5\cdot 661\cdot 2243\cdot 8447$\\
15  &amp; $2^2\cdot 234819684019$\\
16  &amp; $349\cdot 8627\cdot 4991479$\\
17  &amp; $2\cdot 5\cdot 13\cdot 281 \cdot 6993808273$\\
18  &amp; $4598708691828421$\\
19  &amp; $2^5\cdot 5^4 \cdot 1579 \cdot 12409 \cdot 222967$\\
20  &amp; $1747509302894800001$\\
21  &amp; $2\cdot 107\cdot 347\cdot 461\cdot 1071999585919$\\
22  &amp; $5\cdot 48259\cdot 3345901481329483$\\
23  &amp; $2^2\cdot 13\cdot 910619\cdot 392147324904187$\\
24  &amp; $5\cdot 1481 \cdot 41813\cdot 287851\cdot 5000304083$\\
25  &amp; $2\cdot 13\cdot 19 \cdot 103\cdot 257\cdot 852007193230945949$\\
26  &amp; $183644977\cdot 1577374632467830901$\\
27  &amp; $2^3\cdot 5\cdot 195531926467458324861473137$\\
28  &amp; $119551\cdot 373670483\cdot 4902230134153477$\\
29  &amp; $2\cdot 5\cdot 635087697166304639150064748979$\\
30  &amp; $13\cdot 127\cdot 13511681593\cdot 8540798558040523807$\\ \hline
\end{tabular}
\caption{Factorization of $a_n$ for $n\leq 30$}\label{fac1}
\end{center}\end{table}

\begin{table}[ht]\begin{center}
\begin{tabular}{| l l |}\hline
$n$ &amp; factor($a_n$)\\ \hline \hline
31  &amp; $2^2\cdot 6793 \cdot 6623384304659\cdot 32818224968844709$\\
32  &amp; $5^2\cdot 157\cdot 329993\cdot 145922492103580626511308757$\\
33  &amp; $2\cdot 19\cdot 37\cdot 1549\cdot 2863807538994480264037164291179$\\
34  &amp; $5\cdot 330679\cdot 1341707 \cdot 2303179\cdot 41504719765549572671$\\
35  &amp; $2^4\cdot 1572242101\cdot 295044907934065408376485520711$\\
36  &amp; $13\cdot 179\cdot 3389\cdot 75793\cdot 2334397613\cdot 191495312948444419631$\\
37  &amp; $2\cdot 5 \cdot 23\cdot 1407281\cdot 30543801770391751614358741298340689$\\
38  &amp; $13\cdot 1307\cdot 22110390324250839623066317140029038949371$\\
39  &amp; $2^2\cdot 5\cdot 47\cdot 373\cdot 1913\cdot 73181\cdot 46498981\cdot$\\
    &amp; $\cdot 6419283046588931936893783$\\
40  &amp; $283\cdot 2207\cdot 452087\cdot 27443371\cdot 10961524829\cdot$\\
    &amp; $\cdot 6899549447021827237$\\
41  &amp; $2 \cdot 23\cdot 67273\cdot 855946423\cdot 9984786337\cdot$\\
    &amp; $\cdot 908531145956175717351149$\\
42  &amp; $5\cdot 51787\cdot 59539\cdot 1306501657\cdot$\\
    &amp; $\cdot 50103819744552590244570709074233$\\
43  &amp; $2^3\cdot 13\cdot 674672980073\cdot 1673513136729517\cdot$\\
    &amp; $\cdot 369560688696281328844439$\\
44  &amp; $5^2\cdot 19\cdot 487\cdot 833893\cdot$\\
    &amp; $\cdot 9898316305621422245445307761627219210689201$\\
45  &amp; $2\cdot 31\cdot 503621\cdot 5349857\cdot$\\
    &amp; $\cdot 514362201527447374617886292288269244810309$\\
46  &amp; $613981\cdot 10339597\cdot$\\
    &amp; $\cdot 622595573454047871500475953343208441017551021$\\
47  &amp; $2^2\cdot 5\cdot 1740373\cdot 25196940506279\cdot$\\
    &amp; $\cdot 211807964674353752193208733585193464069$\\
48  &amp; $262066528371751897\cdot 22100157339031818463$\\
    &amp; $\cdot 1539560451909744956702071$\\
49  &amp; $2\cdot 5\cdot 13\cdot 36948815219\cdot 5938235313533\cdot$\\
    &amp; $\cdot 15317873368507025363816947275444788447$\\
50  &amp; $31\cdot 293\cdot 206506391500393\cdot 31126232036943157\cdot$\\
    &amp; $\cdot 374179843710832651624027922347$\\ \hline
\end{tabular}
\caption{Factorization of $a_n$ for $30 &lt; n\leq 50$}\label{fac2}
\end{center}\end{table}

\section*{Acknowledgements}
The author is most grateful to the friendly referee who pointed out a
mistake in the manuscript and made various most valuable suggestions to
improve the paper.

\begin{thebibliography}{99}

\bibitem{brillhart}
J. Brillhart, D. H. Lehmer and J. L. Selfridge, New primality criteria
and factorizations of $2^m\pm 1$, \textit{Math. Comp.} \textbf{29}
(1975), 620--647.

\bibitem{hardy}
G. H. Hardy and E. L. Wright, \textit{An Introduction to the Theory of
Numbers}, Oxford University Press, 1979

\bibitem{lenstra}
H. W. Lenstra, Jr., Factoring integers with elliptic curves,
\textit{Ann. Math.} \textbf{126} (1987), 649--673.

\bibitem{sloane}
Online Encyclopedia of Integer Sequences (OEIS), electronically published at: 
\href{http://www.research.att.com/~njas/sequences}{\tt http://www.research.att.com/$\,\tilde{}\,$njas/sequences/} 

\bibitem{wagstaff}
S.S. Wagstaff, Divisors of Mersenne numbers, \textit{Math. Comp.}
\textbf{40} (1983), 385--397.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11Y05; Secondary 11Y55.

\noindent \emph{Keywords: factorization, integer sequence, prime number}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A056542} and \seqnum{A070213}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 2 2004;
revised version received June 24 2005. 
Published in {\it Journal of Integer Sequences}, July 6 2005.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>