\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<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>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$ & $n$ with $p|a_n$ & $p$ & $n$ with $p|a_n$ \\ \hline\hline 2 & 3 & 113 & 163\\ 5 & 7, 9 & 127 & 135\\ 13 & 17, 23, 25 & 131 & 153, 164\\ 19 & 25, 33 & 137 & 144, 153\\ 23 & 37, 41 & 149 & 218\\ 29 & 52 & 163 & 168\\ 31 & 45, 50 & 167 & 242\\ 37 & 53, 71, 73 & 173 & 336\\ 41 & 78 & 179 & 351\\ 43 & 62 & 181 & 276\\ 59 & 100 & 193 & 250, 255\\ 71 & 81, 120 & 197 & 228, 297\\ 83 & 157 & 211 & 269, 357, 391, 415\\ 97 & 123 & 223 & 363\\ 103 & 109 & 227 & 411, 436\\ 107 & 158 & 239 & 418\\ 109 & 196, 213 & 251 & 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<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 & = & 17\\ a_8 & = & 28961\\ a_{18} & = & 4598708691828421\\ a_{20} & = & 1747509302894800001\\ a_{70} & = & \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} & = & \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} & = & \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} & = & \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 & = & 2^2 \cdot 3 \cdot 13 \cdot 29 \cdot 4793 \cdot 15227 \cdot 20422008121 \cdot\\ & & \cdot 688270315985433959 \cdot 28276698587131486301 \cdot \\ & & \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