<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
% pyth0805.tex   For Jour. Int. Seq.  Sept 1,2001 

\documentclass{amsart}

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


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

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

\numberwithin{equation}{section}

%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

\begin{document}

%For submitting manuscript add next 2 lines 
%\hoffset -.5 in
%\hsize 6 in
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo23.eps}
\vskip 1cm
{\LARGE\bf Prime Pythagorean triangles}
\vskip 1.5cm

\large Harvey Dubner \\ \smallskip
449 Beverly Road, Ridgewood, New Jersey 07450 \\ \medskip

Tony Forbes \\ \smallskip
Department of Pure Mathematics, The Open University, Walton Hall, Milton Keynes MK7 6AA, United Kingdom \\ \medskip

Email addresses:
\href{mailto:hdubner1@compuserve.com}{hdubner1@compuserve.com}
and
\href{mailto:tonyforbes@ltkz.demon.co.uk}{tonyforbes@ltkz.demon.co.uk}
\vskip2.5cm
{\bf Abstract}
\end{center}
{\em A prime Pythagorean triangle has three integer sides of which the 
hypotenuse and one leg are primes. 
In this article we investigate their properties and distribution. 
We are also interested in finding chains 
of such triangles, where the hypotenuse of one triangle is 
the leg of the next in the sequence. 
We exhibit a chain of seven 
prime Pythagorean triangles and we include a brief
discussion of primality proofs for 
the larger elements (up to 2310 digits) of the associated 
set of eight primes.
}

\vspace*{+.1in}
\noindent 1991 {\it Mathematics Subject Classification}: Primary 11A41

\noindent {\it Keywords}: Pythagorean triangles, prime numbers, primality proving

\section{Introduction}

While investigating the distribution of special forms of primes, the first 
author accidently came across a conjecture about Pythagorean triangles 
(right triangles with integral sides).  The conjecture, based on the famous 
Conjecture (H) of Sierpi\'nski and Schinzel, states that there is an 
infinite number of Pythagorean triangles which have a leg and hypotenuse 
both prime \cite[page 408]{Rib95}. 



Pythagorean triangles have been the subject of much recreational material
\cite{AB66} as well as the basis of some of the most important and fundamental 
topics in number theory.  However, we could not find any significant 
references to such two-prime Pythagorean triangles, and hoping 
that we had found a new topic to study we enthusiastically started

\begin{enumerate}
\item developing appropriate theory and computer programs;
\item searching for large two-prime triangles;
\item searching for sequences of two-prime triangles where the 
hypotenuse of the previous triangle becomes the leg of the next one.
\end{enumerate}

The largest two-prime Pythagorean triangle that was found had a leg of 
5357 digits and an hypotenuse of 10713 digits.
It soon became apparent that finding sequences of triangles was 
exceptionally interesting and challenging.  Eventually a sequence of seven
triangles was found.  More significant than the seven triangles is the 
improvement by the second author of the general method, APRCL, for primality
proving so that the seventh hypotenuse of 2310 digits could be proved prime.  


\section{Theory}

A two-prime Pythagorean triangle, $A^2+B^2=C^2$, must be primitive, so that
\begin{equation*}
A=u^2-v^2, \qquad  B=2uv, \qquad C=u^2+v^2, 
\end{equation*}
with $\gcd(u,v)=1$, and $u,v$ of different parity. Since $A=(u+v)(u-v)$, 
for $A$ to be prime it is necessary that $(u-v)=1$ so that 
\begin{equation*}
A=2v+1, \qquad B=2v^2+2v, \qquad C=2v^2+2v+1.  
\end{equation*}
Thus
\begin{equation}
C=\frac{A^2+1}{2}.
\end{equation}
Note that the even leg is only one less than the hypotenuse.  The triangles 
get quite thin as $A$ increases.

To find two-prime Pythagorean triangles it is necessary to find pairs of 
primes $A,C$ that satisfy the above equation.  Table 1 lists the smallest 
two-prime Pythagorian triangles.    

\begin{table}[htb]
\caption{Pythagorean triangles with two prime sides}
\label{tab:1} 
\begin{tabular}{|r|*3{r}|}
\hline
rank&amp; prime leg&amp; even leg&amp; hypotenuse\\ 
\hline
1&amp;     3&amp;      4&amp;       5\\ 
2&amp;     5&amp;     12&amp;       13\\ 
3&amp;    11&amp;      60&amp;      61\\ 
4&amp;    19&amp;     180&amp;      181\\ 
5&amp;    29&amp;     420&amp;      421 \\
6&amp;    59&amp;    1740&amp;      1741\\ 
7&amp;    61&amp;    1860&amp;       1861   \\
8&amp;    71&amp;    2520&amp;       2521\\ 
9&amp;    79&amp;    3120&amp;       3121\\
10&amp;      101&amp;       5100&amp;       5101\\ 
\hline
100&amp;     4289&amp;    9197760&amp;    9197761\\
\hline
1000&amp;    91621&amp; 4197203820&amp; 4197203821 \\
\hline
\end{tabular}
\end{table}     

Small triangles are easy 
to find by a simple search, but finding large triangles with thousands of 
digits is complicated by the difficulty of proving true primality of the
hypotenuse, $C$.  However, if $(C-1)$ has many factors then it is easy to 
prove primality using \cite{BLS75}, assuming that the factored part of 
$(C-1)$ exceeds $\root 3 \of C$.  Since
\begin{equation}
C-1=\frac{A^2+1}{2}-1=(A^2-1)/2=(A-1)(A+1)/2,
\end{equation}
by picking an appropriate form for $A$, then $(A-1)$ can be completely 
factored so that $(C-1)$ will be about 50\% factored.  

Using the form $A=k\cdot 10^n +1$, a computer search of a few days gave the 
following large triangle:
\begin{equation*} 
A=491140 \cdot 10^{1300}+1, \text{\quad 1306 digits,\qquad $C=2612$ digits.}  
\end{equation*}
 
A few days after this result was posted to the NMBRTHRY list we received a 
message from Iago Camboa announcing a much larger triangle:
\begin{equation*}
A=1491 \cdot 2^{17783}+1, \text {\quad 5357 digits, \qquad $C=10713$ digits.}
\end{equation*}
He cleverly used a previously computed list of primes as a source for $A$
thus eliminating the large amount of time required to find the first prime.

\section{Two-prime Pythagorean triangle sequences}

It is possible to find a series of primes, $P_0, P_1, P_2, ..., P_k, ..., P_n$
such that 
\begin{equation}
P_{k+1}=\frac{P_k^2+1}{2}.
\end{equation} 
This represents a sequence of $n$ two-prime triangles where $P_k$ is the 
hypotenuse of the $k$-th triangle and the leg of the $(k+1)$-th triangle.
Each $P$ has about twice the number of digits as the previous $P$.  
Table 2 is a list of the smallest sets of two sequential prime Pythagorean 
triangles. 

\begin{table}[htb]
\caption{Two sequential prime Pythagorean triangles}
\label{tab:2} 
\begin{tabular}{|r|*3{r}|*3{r}|}
\hline
 &amp; \multicolumn{3}{c|}{triangle 1}
 &amp; \multicolumn{3}{c|}{triangle 2}\\
\hline
 1&amp;     3&amp;      4&amp;      5&amp;      5&amp;        12&amp;         13\\ 
 2&amp;    11&amp;     60&amp;     61&amp;     61&amp;      1860&amp;       1861\\ 
 3&amp;    19&amp;    180&amp;    181&amp;    181&amp;     16380&amp;      16381\\ 
 4&amp;    59&amp;   1740&amp;   1741&amp;   1741&amp;   1515540&amp;    1515541\\ 
 5&amp;   271&amp;  36720&amp;  36721&amp;  36721&amp; 674215920&amp;  674215921\\
 6&amp;   349&amp;  60900&amp;  60901&amp;  60901&amp; 1854465900&amp; 1854465901\\
 7&amp;   521&amp;   135720&amp; 135721&amp; 135721&amp; 9210094920&amp; 9210094921\\ 
 8&amp;   929&amp;  431520&amp;  431521&amp; 431521&amp; 93105186720&amp; 93105186721\\
\hline 
\end{tabular}
\end{table} 

Table 3 is a list of the starting primes for the smallest prime Pythagorean
sequences for two, three, four and five triangles.  These were found by 
straight forward 
unsophisticated searching and took about 10 computer-days (Pentium/200), 
mostly for finding five triangles.  


\begin{table}[htb]
\caption{Starting prime for smallest prime Pythagorean sequences}
\label{tab:3} 
\begin{tabular}{|r|r|r|r|r|}
\hline

&amp;2 triangles&amp; 3 triangles&amp; 4 triangles&amp; 5  triangles\\
\hline

   1&amp;  3&amp;  271&amp;  169219&amp;  356498179 \\ \hline
   2&amp;  11&amp;  349&amp;  1370269&amp;  432448789\\ \hline
   3&amp;  19&amp;  3001&amp;  5965699&amp;  5380300469 \\ \hline
   4&amp;  59&amp;  10099&amp;  15227879&amp;  10667785241 \\ \hline
   5&amp;  271&amp;  11719&amp;  17750981&amp;  11238777509\\ \hline
   6&amp;  349&amp;  12281&amp;  19342559&amp;  12129977791\\ \hline
   7&amp;  521&amp;  25889&amp;  21828601&amp;  23439934621\\ \hline
   8&amp;  929&amp;  39901&amp;  24861761&amp;  28055887949\\ \hline
   9&amp;  1031&amp;  46399&amp;  27379621&amp;  33990398249\\ \hline
  10&amp;  1051&amp;  63659&amp;  34602049&amp;  34250028521\\ \hline
  11&amp;  1171&amp;  169219&amp;  39844619&amp;  34418992099\\ \hline
  12&amp;  2381&amp;  250361&amp;  48719711&amp;  34773959159\\ \hline
  13&amp;  2671&amp;  264169&amp;  50049281&amp;  34821663421\\ \hline
  14&amp;  2711&amp;  287629&amp;  51649019&amp;  36624331189\\ \hline
  15&amp;  2719&amp;  289049&amp;  52187371&amp;  40410959231\\ \hline
  16&amp;  3001&amp;  312581&amp;  52816609&amp;  43538725229\\ \hline
  17&amp;  3499&amp;  353081&amp;  58026659&amp;  47426774869\\ \hline
  18&amp;  3691&amp;  440681&amp;  73659239&amp;  48700811941\\ \hline
  19&amp;  4349&amp;  473009&amp;  79782821&amp;  49177751131\\ \hline
  20&amp;  4691&amp;  502501&amp;  86569771&amp;  59564407571\\ \hline
\end{tabular}
\end{table} 

Finding the starting prime for the smallest prime sequence of six triangles 
took about 120 computer days.\\

\qquad \qquad    $P_0$ for 6 triangles $=2500282512131$.\\

Next, we attempted to derive the number of $n$ triangle sequences that 
could be expected.  If the $(n+1)$ numbers that make up the $n$ triangles 
were selected randomly but were of the proper size then the probability 
that $P$ is the start of $n$ triangles is
\begin{equation} 
Q(P,n)=\prod_0^n \frac{1}{\log P_i}=\prod_0^n \frac{1}{2^i(\log P)}
=\frac{1}{2^{n(n+1)/2}(\log P)^{n+1}}.
\end{equation}
However, there are correlations between the primes that affect the 
prime probabilities.  It is easy to show from equation (2.1) that  
$P_0$ can only end in 1 or 9, which elininates half the possible $P_0$'s,
and assures that all subsequent potential primes cannot be divisible by 2, 3 
or 5. Thus, the probability of each subsequent number being prime is 
increased by the factor $(2/1)(3/2)(5/4)=3.75$.  The probability that $P$
is the start of $n$ prime triangles now becomes,
\begin{equation}
Q(P,n)=\frac{0.5(3.75)^n}{2^{n(n+1)/2}(\log P)^{n+1}}.
\end{equation}
The expected number of prime triangles up to a given $P_0$ is 
\begin{equation}
E(P_0,n)=\sum_{P=3}^{P_0} Q(P,N)
=\frac{0.5(3.75)^n}{2^{n(n+1)/2}} \sum_{P=3}^{P_0}\frac{1}{(\log P)^{n+1}}.
\end{equation}
The last summation can be approximated by an integral, which after integrating 
by parts becomes,
\begin{equation*}
R(P,n)=\frac{1}{n!}Li(P)
-\frac{1}{n!}\frac{P}{\log P}-\dots-\frac{1}{n(n-1)}\frac{P}{(\log P)^{(n-1)}}
-\frac{1}{n}\frac{P}{(\log P)^n},
\end{equation*}
where $Li(P)$ is the logarithmic integral.  Equation (3.4) now becomes
\begin{equation}
E(P_0,n)=\frac{0.5(3.75)^n}{2^{n(n+1)/2}}R(P_0,n)(1.3)^n \ .
\end{equation}
Note the inclusion of a correction factor, $(1.3)^n$.
As is discussed in the following section on sieving, there are other 
correlations between the primes which affect the expectation.  These are 
difficult to derive theoretically so we determined it empirically.    
Table 4 compares the estimated and actual number of triangles
found.  The corrected estimate appears adequate to assist in estimating the 
search time for seven prime Pythagorean triangles.

\begin{table}[htb]
\caption{Estimated and actual number of prime Pythagorean triangles}
\label{tab:4}
\begin{tabular}{|c|r{r}{r}r|}
\hline
triangles&amp; &amp; &amp; &amp; corrected\\
$n$&amp; $P_0 \quad $&amp; actual&amp; estimate&amp; estimate\\
\hline
1&amp; 130000&amp; 1302&amp; 1090&amp; 1420\\ 
2&amp; 1980000&amp; 1005&amp; 741&amp; 1252\\
3&amp; $10^8$&amp; 953&amp; 469&amp; 1030\\
4&amp; $18\cdot 10^8$&amp; 205&amp; 53&amp; 151\\ 
5&amp; $63\cdot 10^9$&amp; 21&amp; 4&amp; 15\\
6&amp; $28\cdot 10^{12}$&amp; 1&amp; 0.14&amp; 0.7\\
\hline
\end{tabular}
\end{table}

Next, we use equation (3.5) to estimate the smallest $P_0$ that will 
give seven triangles.  The following table shows we can expect that $P_0$
for seven triangles will be about 6700 times larger than $P_0$ for six 
triangles.  Using performance data from the search for six triangles, 
this means that the search for the smallest sequence of seven prime 
Pythagorean triangles could be expected to take about 200 computer-years!
       

\begin{center}
\begin{tabular}{|c|l|l|}
\hline
$n$ &amp; $P_0$ for expectation=1 &amp; actual $P_0$\\
\hline 
2 &amp; 28 &amp; 3\\
3 &amp; 1,350 &amp; 271\\
4&amp; 1,000,000&amp; 169, 219\\
5&amp; $1.5\cdot 10^9$&amp; $3.5\cdot 10^8$ \\
6&amp; $4.0\cdot 10^{12}$&amp; $2.5\cdot 10^{12}$\\
7&amp; $2.7\cdot 10^{16}$&amp; \\
\hline
\end{tabular}
\end{center}

It was clear that the search for the smallest sequence of seven triangles 
as presently constituted was impractical.  For every $P_0$ the search method
included testing by division to see if each of the $(n+1)$ potential primes 
was free of small factors.       
The second author then proposed an efficient sieving method that 
limited the search to sequences that had a high probability of success.
This made a search for seven triangles reasonable.

\section{The Sieve}

A set of seven Pythagorean triangles with the desired properties 
is equivalent to a chain of eight primes, 
$P_{0}, P_{1}, \dotsc, P_{7}$, linked by the condition 
$P_{i+1}= ( P_{i}^{2}+1 )/2$, $i = 0, 1, \dotsc, 6$. 

The purpose of the sieve is to eliminate from further consideration 
numbers $P_{0}$ for which either $P_{0}$ itself or one of 
the numbers $P_{i}$, $i = 1, 2, \dotsc, 7$, is divisible by a small 
prime. Let $q$ be an odd prime and suppose $P$ is to be considered 
as a possible value of $P_{0}$. Clearly, we can reject $P$ if 
$P \equiv 0 \pmod q$. Furthermore, we can reject $P$ 
if $P_{1}$ is divisible by $q$, that is, if 
\begin{equation*}
P \equiv \sqrt{-1}\pmod q ,
\end{equation*}
on the assumption that $\left(\frac{-1}{q}\right) = 1$. 
Continuing 
in this way, we can reject $P$ if 
\begin{equation*}
P \equiv \sqrt{2\sqrt{-1}-1} \pmod q
\end{equation*}
(for then $P_{2}$ is divisible by $q$), 
or if 
\begin{equation*}
P \equiv \sqrt{2\sqrt{2\sqrt{-1}-1}-1} \pmod q,
\end{equation*}
and so on, provided that the various square roots 
$\pmod q$ exist. 
In each case, where there is a square root 
$\pmod q$ there are two possible values and hence two extra 
residues $\pmod q$ that can be eliminated.

For prime $q$, we compute the set $E(q)$ of forbidden residues 
$\pmod q$ as follows. Start with 
$E_{0}(q) = \{0\}$. Given 
$E_{i}(q)$, let
\begin{equation*}
E_{i+1} = \left\{ \pm\sqrt{2e-1}\pmod q: e \in E_{i} \: {\rm and} \: \left( \frac{2e-1}{q} \right) = 1 \right\}.
\end{equation*}
Then $E(q)$ is the union of $E_{0}(q)$, $E_{1}(q)$, $\dotsc$, 
$E_{7}(q)$. 
In Table~\ref{tab:eq} 
we list $E(q)$ for the first few primes $q \equiv 1 \pmod 4$.

\begin{table}[htb]
\caption{$E(q)$}
\label{tab:eq}
\begin{tabular}{|r|c|}
\hline
$q$ &amp; $E(q)$\\
\hline
5 &amp; \{0, 2, 3\} \\
\hline
13 &amp; \{0, 3, 5, 8, 10\} \\
\hline
17 &amp; \{0, 3, 4, 5, 12, 13, 14\} \\
\hline
29 &amp; \{0, 2, 3, 5, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 24, 26, 27\} \\
\hline
37 &amp; \{0, 6, 8, 14, 23, 29, 31\} \\
\hline
41 &amp; \{0, 9, 32\} \\
\hline
53 &amp; \{0, 4, 14, 16, 17, 18, 19, 22, 23, 30, 31, 34, 35, 36, 37, 39, 49\} \\
\hline
61 &amp; \{0, 11, 50\} \\
\hline
73 &amp; \{0, 23, 27, 46, 50\} \\
\hline
89 &amp; \{0, 9, 26, 27, 30, 34, 37, 38, 39, 40, 41, 44, 45, 48, 49, 50, 51, 52, \\
 &amp; 55, 59, 62, 63, 80\} \\
\hline
97 &amp; \{0, 7, 22, 25, 72, 75, 90\} \\
\hline
101 &amp; \{0, 7, 10, 12, 15, 16, 22, 23, 25, 26, 34, 35, 37, 38, 50, 51, 63, 64, \\
 &amp; 66, 67, 75, 76, 78, 79, 85, 86, 89, 91, 94\} \\
\hline
109 &amp; \{0, 33, 76\} \\
\hline
113 &amp; \{0, 2, 15, 46, 54, 59, 67, 98, 111\} \\
\hline
137 &amp; \{0, 22, 37, 100, 115\} \\
\hline
149 &amp; \{0, 44, 105\} \\
\hline
157 &amp; \{0, 10, 28, 31, 126, 129, 147\} \\
\hline
173 &amp; \{0, 32, 80, 93, 141\} \\
\hline
181 &amp; \{0, 2, 9, 19, 30, 33, 41, 47, 54, 56, 64, 78, 80, 88, 93, 101, 103, 117, \\
 &amp; 125, 127, 134, 140, 148, 151, 162, 172, 179\} \\
\hline
193 &amp; \{0, 57, 81, 112, 136\} \\
\hline
197 &amp; \{0, 14, 37, 94, 103, 160, 183\} \\
\hline
229 &amp; \{0, 18, 19, 30, 48, 54, 59, 69, 91, 107, 110, 119, 122, 138, 160, 170, \\
 &amp; 175, 181, 199, 210, 211\} \\
\hline
233 &amp; \{0, 3, 5, 7, 12, 13, 16, 21, 25, 27, 30, 42, 43, 44, 48, 52, 53, 55, 61, \\
 &amp; 67, 71, 80, 85, 89, 101, 104, 115, 118, 129, 132, 144, 148, 153, 162, 166, \\
 &amp; 172, 178, 180, 181, 185, 189, 190, 191, 203, 206, 208, 212, 217, 220, 221, \\ 
 &amp; 226, 228, 230\} \\
\hline
241 &amp; \{0, 64, 177\} \\
\hline
257 &amp; \{0, 16, 51, 206, 241\} \\
\hline
269 &amp; \{0, 82, 187\} \\
\hline
277 &amp; \{0, 8, 52, 60, 106, 171, 217, 225, 269\} \\
\hline
281 &amp; \{0, 53, 228\} \\
\hline
293 &amp; \{0, 4, 121, 138, 155, 172, 289\} \\
\hline
313 &amp; \{0, 7, 21, 25, 92, 221, 288, 292, 306\} \\
\hline
317 &amp; \{0, 17, 23, 24, 31, 44, 50, 52, 56, 74, 97, 114, 115, 126, 130, 134, \\
 &amp; 141, 142, 145, 153, 164, 172, 175, 176, 183, 187, 191, 202, 203, 220, 243, \\
 &amp; 261, 265, 267, 273, 286, 293, 294, 300\} \\
\hline
337 &amp; \{0, 21, 31, 34, 50, 71, 73, 90, 110, 114, 116, 144, 148, 153, 157, 162, \\
 &amp; 175, 180, 184, 189, 193, 221, 223, 227, 247, 264, 266, 287, 303, 306, 316\} \\
%\hline
%349 &amp; \{0, 8, 10, 12, 16, 18, 20, 23, 26, 27, 39, 46, 57, 63, 74, 80, 84, 102, \\
% &amp; 108, 109, 111, 115, 120, 121, 124, 133, 135, 136, 139, 142, 152, 163, 164, \\
% &amp; 185, 186, 197, 207, 210, 213, 214, 216, 225, 228, 229, 234, 238, 240, 241, \\
% &amp; 247, 265, 269, 275, 286, 292, 303, 310, 322, 323, 326, 329, 331, 333, 337, \\
% &amp; 339, 341\} \\
%\hline
%353 &amp; \{0, 14, 18, 29, 35, 42, 57, 68, 78, 89, 93, 140, 141, 212, 213, \\
% &amp; 260, 264, 275, 285, 296, 311, 318, 324, 335, 339\} \\
%\hline
%373 &amp; \{0, 4, 10, 22, 56, 58, 61, 104, 110, 136, 178, 195, 237, 263, 269, \\
% &amp; 312, 315 317 351 363 369\} \\
%\hline
%389 &amp; \{0, 115, 274\} \\
%\hline
%397 &amp; \{0, 42, 51, 63, 103, 110, 120, 144, 152, 155, 159, 238, 242, 245, \\
% &amp; 253 277 287 294 334 346 355\} \\
\hline
\end{tabular}
\end{table}

Now let
\begin{equation*}
P = NQ+H,
\end{equation*}
where $Q$ is the product of small primes and $H$ 
is allowed to run through all the permitted residues $\pmod Q$. 
We sieve the numbers $N$. That is, we start with an interval 
$N_{0} \leq N &lt; N_{1}$ and for each sieving prime $q$, 
$\gcd (q, Q) = 1$, we remove all those 
$N \in [ N_{0} , N_{1})$ for which $NQ+H$ is divisible by $q$. 

We split $Q$ into pairwise coprime divisors $m_{0}$, 
$m_{1}$, $\dotsc$, $m_{r}$. For each divisor $m_{j}$ of $Q$, 
$j = 0, 1, \dotsc, r$, we make a list of the permitted residues 
$\pmod{m_j}$; $h$ is a permitted residue 
$\pmod{m_j}$ if $h$ is not zero 
$\pmod{m_j}$ and if the function 
$h \rightarrow (h^{2}+1)/2 \pmod{m_j}$ does not 
produce zero $\pmod{m_j}$
during the first seven iterations. 
The permitted residues $H \pmod Q$ are constructed from permitted 
residues $h \pmod{m_j}$ using the Chinese Remainder Theorem. 
It works well if $Q$ is the product of primes which have small percentages 
of permitted residues. From this perspective the best primes, in 
descending order of merit, turn out to be: 29 (34\%), 5 (40\%), 2 (50\%), 
17 (59\%), 13 (62\%), 3 (67\%), 53 (68\%), 101 (71\%), 89 (74\%) and 233 
(77\%).

For the actual search we chose $Q=21342962305470$, 
with divisors 6630 = $2 \cdot 3 \cdot 5 \cdot 13 \cdot 17$, 
29, 89, 101, 53, and 233. The number of values of $H \pmod Q$ 
turns out to be $320 \cdot 10 \cdot 66 \cdot 72 \cdot 36 \cdot 180$ = 
98537472000, the indicated factors of this product being the numbers of permitted 
residues modulo the corresponding factors of $Q$. 

The construction of the sieve and the method of computing 
$H \pmod Q$ were based on computer programs designed for finding prime 
$k$-tuplets; see \cite{Forbes99} for the details. 
We set up a table of sieving primes $q$ 
together with pre-computed values of $-1/Q \pmod q$ as well as, 
for $q \equiv 1 \pmod 4$, $e/Q \pmod q$ 
for each pair $e$, $q-e$ in $E(q)$.
We can then rapidly calculate the index of the first $N$ to be removed 
from the sieve array for $P \equiv e \pmod q$:
$e/Q - H/Q - N_{0} \pmod q$.

The program also allows 
us to limit the size of primes $q \equiv 3 \pmod 4$ used by the sieve. 
One reason for doing so would be to give priority to primes 
$q \equiv 1 \pmod 4$; they have more residues for sieving and 
therefore one would expect them to be in some sense more efficient. 
In fact it was found by experiment that if $P$ has about 19 digits, a 
sieve limit $L_{0} = 20000$ for $q \equiv 3 \pmod 4$ and 480000 
for $q \equiv 1 \pmod 4$ was approximately optimal.

Further performance improvements are possible by limiting the influence 
of primes $q \equiv 1 \pmod 4$. For each $P$ that survives 
the sieve we do a probable-primality test, 
$2^{P} \equiv 2 \pmod P$, on $P$ as well as, if $P$ 
turns out to be a probable-prime, 
the numbers that follow $P$ in the chain, stopping as soon as a 
composite is found. The 
effort required to perform the probable-primality test increases by 
a factor of about eight as we move from $P_{i}$ to $P_{i+1}$. 
Therefore it might be better if priority were given to sieving 
primes $q$ and residues $e \pmod q$ which would eliminate composite 
numbers from the larger elements of the chain. 

For controlling the effect of primes $q \equiv 1 \pmod 4$ 
we provided a set of parameters $L_{1}$, 
$L_{2}$, $\dotsc$. If $q \equiv 1 \pmod 4$ is a sieving prime and 
$e \in E_{i}(q)$ then we do not use residue 
$e \pmod q$ for sieving unless $q&lt;L_{i}$. As a result of a certain 
amount of experimentation we found that the optimum sieving rate 
occurs with the limits set approximately as follows: $L_{1} = 120000$, 
$L_{2} = 240000$, $L_{3} = 360000$, together with a limit 
$L_{0} = 20000$ for primes $\equiv 3 \pmod 4$ and an overall sieve limit of 
480000. From these values we can compute 
an expected survival rate of 
\begin{equation*}
\prod_{q \text{ prime}} \frac{q - \nu_{q}}{q} = \frac{1}{3770},
\end{equation*}
approximately, where $\nu_{q}$ 
is the number of residues $\pmod q$ used by the sieve.

\section{Eight Primes}

In September 1999 the search was successful and this 
chain of eight probable primes was found:
\begin{eqnarray*}
P_{0}&amp; =&amp; 2185103796349763249 \text{\qquad (19 digits),}\\
P_{1}&amp; =&amp; ( P_{0}^{2}+1)/2 \text{\qquad (37 digits),}\\
P_{2}&amp; =&amp; ( P_{1}^{2}+1)/2 \text{\qquad (73 digits),}\\
P_{3}&amp; =&amp; ( P_{2}^{2}+1)/2 \text{\qquad (145 digits),}\\
P_{4}&amp; =&amp; ( P_{3}^{2}+1)/2 \text{\qquad (289 digits),}\\
P_{5}&amp; =&amp; ( P_{4}^{2}+1)/2 \text{\qquad (579 digits),}\\
P_{6}&amp; =&amp; ( P_{5}^{2}+1)/2 \text{\qquad (1155 digits),}\\
P_{7}&amp; =&amp; ( P_{6}^{2}+1)/2 \text{\qquad (2310 digits).}
\end{eqnarray*}

The search program was designed to run on standard IBM PCs. 
We employed about 15 such machines, 
with clock speeds ranging from 200 MHz to 400 MHz. The faster computers 
were sieving and testing numbers at rates of about ten billion 
per hour.
We also found 174 additional chains of seven (probable) primes. 

\section{Primality Proofs}

The first six numbers, $P_{0}$, $P_{1}$, $\dotsc$, $P_{5}$, 
as well as other small primes mentioned 
in this section are easily verified by 
the UBASIC \cite{Caldwell93} program APRT-CLE, a 
straightforward implementation of the APRCL test. 
For $i=6$ and 7 we attempt to factorize 
\begin{equation*}
P_{i}-1  =  (P_{0}-1) \prod_{j=0}^{i-1} \frac{1}{2} \left( P_{j}+1 \right).
\end{equation*}
Thus
\begin{eqnarray*}
P_{0}-1 &amp; = &amp; 2^{4} \cdot 233 \cdot 586132992583091,\\
( P_{0} + 1 )/2 &amp; = &amp; 3^{2} \cdot 5^{3} \cdot 13 \cdot 761 \cdot 19087 \cdot 5143087,\\
( P_{1} + 1 )/2 &amp; = &amp; 7^{2} \cdot 1063 \cdot 189043 \cdot 7552723 \cdot 113558719 \cdot 141341652553,\\
( P_{2} + 1 )/2 &amp; = &amp; 7058053 \cdot 5848063479673576700713235221 \\
           &amp; &amp;  \cdot 34520041584369005634844907730019249777,\\ 
( P_{3} + 1 )/2 &amp; = &amp; 2179 \cdot 1847645923 \cdot C_{132},\\
( P_{4} + 1 )/2 &amp; = &amp; 307 \cdot 769 \cdot 262513 \cdot P_{278},\\
( P_{5} + 1 )/2 &amp; = &amp; 108139 \cdot 11360649709 \cdot 5586562264501 \cdot C_{550}, \\
( P_{6} + 1 )/2 &amp; = &amp; 4177 \cdot 1372052449 \cdot 5098721569  \cdot 84098816095916212867 \cdot C_{1113},
\end{eqnarray*}
where $C_{132}$, $C_{550}$ and $C_{1113}$ are composite numbers 
of 132, 550 and 1113 digits, respectively, and $P_{278}$ is a 
278-digit prime:
\begin{eqnarray*}
P_{278} &amp; = &amp; 66505518540598996114987486506055236521044267373138 \\
        &amp;   &amp; 69473288000457727001877127498646545001634613677898 \\
        &amp;   &amp; 53932112480508999228232340454335875401889420451888 \\
        &amp;   &amp; 17780482079524485531037464472393979852934170207932 \\
        &amp;   &amp; 02663155485302406204947222346461607409301255277393 \\
        &amp;   &amp; 4788467292248055697961196019.
\end{eqnarray*}
The 28-digit factor of $P_{2}+1$ and the 20-digit 
factor of $P_{6}+1$ were found by Manfred Toplic and Paul 
Zimmermann.

Since we have a 41\% partial factorization of $P_{6}-1$ 
we can establish the primality of $P_{6}$ by the methods 
of Brillhart, Lehmer and Selfridge \cite{BLS75}. (Similarly 
a 77\% factorization of $P_{5}-1$ provides an alternative 
proof for $P_{5}$.)

It remains to deal with $P_{7}$. 
We do not have enough prime factors of $P_{7}-1$ for a simple 
proof, so we use a combination of methods. Suppose $d &lt; P_{7}$ is a 
prime factor of $P_{7}$. The proof that no such $d$ exists 
proceeds in several stages. 

Gathering together the prime factors of $P_{7}$ listed above, let 
\begin{eqnarray*}
F_{1} &amp; = &amp; 11364028773118678645863393880225035110068188490680 \\
      &amp;   &amp; 74284625807644534721210969640169863192044176288720 \\
      &amp;   &amp; 57382836214336492569310719940321645143241641366672 \\
      &amp;   &amp; 31704620613678520580684280352992373327229897947340 \\
      &amp;   &amp; 09917692032743575475918022578947700337216860293874 \\
      &amp;   &amp; 96561498464943981086970289943873321681460108830000 \\
      &amp;   &amp; 00131801406514260770804840415255291401064877989705 \\
      &amp;   &amp; 76202962420323563098312300324091122817224414751412 \\
      &amp;   &amp; 15123765209184430598589590008879997663256918503367 \\
      &amp;   &amp; 07250451432160496252649191808276871593840887080642 \\
      &amp;   &amp; 91103468534974000 \text{  (517 digits).}
\end{eqnarray*}
Then, after confirming that the conditions of Pocklington's 
theorem \cite{Pocklington15} hold, we have
\begin{equation}
\label{eq:d1}
d \equiv 1 \pmod{F_1}.
\end{equation}

Similarly, by Morrison's theorem \cite[Theorem 16]{BLS75}, 
\begin{equation}
\label{eq:d2}
d \equiv \pm 1 \pmod{F_2},
\end{equation}
where $F_{2}=43^{2} \cdot 73 = 134977$. 

Next, we confirm that the conditions 
for the APRCL test (see, for example, Cohen and A. K. Lenstra \cite{CohenLenstra87}
or Cohen and H. W. Lenstra \cite{CohenLenstra84}) are 
satisfied with the prime powers $p^{k}$:
$\{ 2^{5}, 3^{3}, 5^{2}, 7, 11, 13 \}$, and primes $q$:
$\{$11, 17, 19, 23, 29, 31, 37, 41, 53, 61, 67, 
71, 79, 89, 97, 101, 109, 113, 127, 131, 151, 157, 181, 199, 211, 
241, 271, 281, 313, 331, 337, 353, 379, 397, 401, 421, 433, 463, 521, 
541, 547, 601, 617, 631, 661, 673, 701, 757, 859, 881, 911, 937, 991, 
1009, 1051, 1093, 1171, 1201, 1249, 1301, 1321, 1801, 1873, 1951, 
2003, 2017, 2081, 2161, 2311, 2341, 2377, 2521, 2731, 2801, 2861, 
2971, 3121, 3169, 3301, 3361, 3433, 3511, 3697, 3851, 4159, 4201, 
4621, 4951, 5281, 5851, 6007, 6301, 6553, 7151, 7393, 7561, 7723, 
8009, 8191, 8317, 8581, 8737, 9241, 9829, 9901, 11551, 11701, 12601, 
13729, 14561, 14851, 15121, 15401, 15601, 16381, 16633, 17551, 18481, 
19801, 20021, 20593, 21601, 21841, 23761, 24571, 25741, 26209, 28081, 
30241, 34651, 36037, 38611, 39313, 42901, 47521, 48049, 50051, 51481, 
54601, 55441, 65521, 66529, 70201, 72073, 79201, 81901, 92401, 93601, 
96097, 103951, 108109, 109201, 110881, 118801, 120121, 123553, 131041, 
140401, 150151, 151201, 180181, 193051, 196561, 200201, 216217, 218401, 
257401, 270271, 300301, 332641, 393121, 415801, 432433, 450451$\}$. 
The result is that 
\begin{equation}
\label{eq:d3}
d \equiv P_{7}^{i} \pmod S \text{  for some  } i=1, 2, \dotsc, T-1,
\end{equation}
where $T = 21621600$ is the product of the $p^{k}$s and 
$S = 8.164364 \cdot 10^{634}$, approximately, is the 
product of the $q$s. 

Let $G=F_{1} F_{2} S$ and observe that 
$F_{1}$, $F_{2}$ and $S$ are pairwise coprime. 
We combine \eqref{eq:d1}, \eqref{eq:d2} and \eqref{eq:d3} 
by the Chinese Remainder Theorem to obtain
\begin{eqnarray*}
d &amp; \equiv &amp; \left( \frac{1}{F_{2} S } \bmod F_{1} \right) F_{2}S + \left( \frac{e}{F_{1} S } \bmod F_{2} \right) F_{1} S
\end{eqnarray*}
\begin{eqnarray*}
 &amp; &amp; + \left( \frac{P_{7}^{i} }{F_{1} F_{2}} \bmod S \right) F_{1} F_{2} \pmod G
\end{eqnarray*}
for some $e = \pm 1$ and $i =1, 2, \dotsc, T-1$. After eliminating all 
possible $d &lt; \sqrt{P_{7}} &lt; G$ by trial division we can conclude that 
$P_7$ is prime.

\section{Acknowledgements}

We would like to thank 
Jeremy Humphries, Manfred Toplic and Paul Zimmermann for 
contributing their own computer 
resources to the search for seven prime Pythagorean triangles. 
We are specifically 
grateful to Paul Zimmermann, who also made his Elliptic Curve program 
available to us for the partial factorization of $P_7-1$.

%\newcommand{\noopsort}[1]{} \newcommand{\singleletter}[1]{#1}
%\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\bibliographystyle{amsplain}
\begin{thebibliography}{1}

\bibitem{AB66}
A.~H.~Beiler, \emph{Recreations In the Theory of Numbers}, 2nd ed.,
Dover Publications, New York, ch. XIV, 1966.

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

\bibitem{Caldwell93}
C.~K.~Caldwell, 
  \emph{UBASIC}, 
  J. Recreational Math., \textbf{25} (1993), 47-54.

\bibitem{CohenLenstra87}
H.~Cohen and A.~K.~Lenstra, 
  \emph{Implementation of a new primality test}, 
  Math. Comp., \textbf{48} (1987), 103-121.

\bibitem{CohenLenstra84}
H.~Cohen and H.~W.~Lenstra, 
  \emph{Primality testing and Jacobi sums}, 
  Math. Comp., \textbf{42} (1984), 297-330.

\bibitem{Forbes99}
Tony~Forbes, \emph{Prime clusters and Cunningham chains}, Math. Comp.,
  \textbf{68} (1999), 1739-1747. 

\bibitem{HW79}
G.~H.~Hardy and E.~M.~Wright, \emph{An Introduction to the Theory of Numbers},
  5th ed., Oxford University Press, 1979.

\bibitem{Pocklington15}
H.~C.~Pocklington, \emph{The determination of the prime or composite 
  nature of large numbers by Fermat's theorem}, 
  Proc. Cambridge Philos. Soc., \textbf{18} (1914-16), 29-30.

\bibitem{Rib95}
P.~Ribenboim, \emph{The New Book of Prime Number Records}, 3rd ed.,
  Springer-Verlag, New York, 1995.

\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Mentions sequences
\htmladdnormallink{A048161}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048161},
\htmladdnormallink{A048270}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048270}
and
\htmladdnormallink{A048295}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048295}.)
}

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received May 6, 2001;
revised version received Sept. 3, 2001.
Published in Journal of Integer Sequences Sept. 13, 2001.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{http://www.
research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{6.5in}{.01in}}


\end{document}
</pre></body></html>