\documentclass{amsart}
%\documentclass{article}
\usepackage[colorlinks=true]{hyperref}

\usepackage{amsfonts,amssymb}
\usepackage{psfig,epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}



%millionc.tex				10:59 AM 11/9/01

% If your version of amsart. cls is version 1.2 (before December 1999), 
% uncomment the following classification.
\renewcommand {\subjclassname}{%
 \textup{2000} Mathematics Subject Classification}

\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}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo126.eps}

\title{A Million New Amicable Pairs}

%    Information for first author
\author{Mariano Garcia}
%    Address of record for the research reported here
\address{Department of Mathematics, Touro College, 27 West 23rd Street, New York, NY 10010}
%\email{hdubner1@compuserve.com}

\vskip 1cm
{\LARGE\bf A Million New Amicable Pairs} \\
\vskip 1.5cm
\large Mariano Garcia \\
Department of Mathematics \\
Touro College \\
27 West 23rd Street, New York, NY 10010

\vskip2.5cm
{\bf Abstract}
\end{center}

{\em
The author has recently discovered over one million new amicable pairs,
bringing to more than two million the total
of known amicable numbers and strengthening the validity of the
as yet unproved conjecture that there are infinitely many
such pairs.
}


\bigskip


Two distinct natural numbers $M$ and $N$ are said to be \emph{amicable} if each is equal to the sum of the 
aliquot parts of the other. This is equivalent to saying that $M$ and $N$ are amicable if 
$\sigma (M) = \sigma(N) = M + N$, where $\sigma (M)$ stands for the sum of all the positive divisors of $M$.

The smallest example of an amicable pair is $(220 = 2^2 \cdot 5 \cdot 11,\  284 = 2^2 \cdot 71)$, which	
was known to the Pythagoreans. For several centuries this was the only known amicable pair. Around the year 1300, 
the amicable pair
$(2^4 \cdot 23 \cdot 47,\  2^4 \cdot 1151)$ 
was discovered by al-Banna and around 1600, Yazdi discovered the pair $(2^7\cdot~191 \cdot~383,\  2^7 \cdot 73727)$. 
The second pair above was later 
rediscovered by Fermat in 1636 and the third pair by Descartes in 1638. The previously listed three pairs
were the only known amicable pairs until Euler \cite{Euler50} discovered 59 additional ones in the middle of the 
eighteenth century. Since then, several mathematicians have discovered amicable numbers, including Legendre, Poulet, 
Gerardin, Seedhoff, Mason, Escott and others.

Until the year 1972, in order to find out what the existing known amicable pairs were, one had to search through the
various individual papers on the subject. But in that year, Lee and Madachy published \cite{LM72}  in the Journal of 
Recreational Mathematics an article entitled ``{The History and Discovery of Amicable Numbers," which dealt with the
history of the subject and listed the 1108 known amicable pairs at that time.

In 1986 Herman te Riele determined and published \cite{te Riele86} all the amicable pairs below $10^{10}$ and,
together with Borho, Battiato, Hoffmann and Lee, published \cite{RBBHL86} a list of known amicable pairs between $10^{10}$
and $10^{52}$. From 1986 to 1995, te Riele became the official "collector" of amicable pairs. People who discovered
amicable pairs sent them to him for verification that the pairs were new and, if so, they were added to the collection.
Te Riele also made up several supplementary lists that he sent to interested people.

In 1995, Pedersen started collecting amicable numbers in the Internet. Today all known amicable pairs can be seen by 
examining the web pages entitled \emph {Known amicable pairs} \cite {Pedersen95}. 

As of January 15, 2001, a total of 843,783 amicable pairs were known. Using essentially the BDE method indicated in 
\cite{Pedersen01}, and based on ideas contained in \cite {BH86}, \cite{Lee68}, and \cite{te Riele84}, the author has
found over one million new amicable pairs during the first three months of the year 2001. In the following paragraphs we
give a brief outline of the method used:

Suppose $E$ and $N$ are natural numbers with $E$ relatively prime to $N$ and to $\sigma(N)-1$, and satisfying the condition
\begin {equation}\tag*{(1)}
 \sigma(E) \cdot \sigma(N) = E \cdot (N + \sigma (N) -1). 
\end {equation}
If now $p, q$ and $r$ are primes such that $E \cdot p \cdot 
q$ and $E \cdot N \cdot r$ constitute an amicable pair, 
we must have $r=(p+1)\cdot (q+1)/\sigma(N) -1$. 
Also, 
\begin {equation}\notag
\sigma(E) \cdot (p+1) \cdot (q+1) =
E \cdot [p\cdot q + N \cdot r] = E \cdot [p \cdot q + N \cdot (p+1)\cdot (q+1) / \sigma (N) -N] 
\end {equation}
and thus
\begin {equation}\tag*{(2)}
\sigma (E) \cdot \sigma (N) \cdot (p+1) \cdot (q+1) = E \cdot [\sigma (N) \cdot p \cdot q + N \cdot (p+1) \cdot (q+1)
-N \cdot \sigma (N)].
\end {equation}
Dividing (2) by (1), we obtain 
\begin {equation}\notag
(p+1) \cdot (q+1) = [\sigma (N) \cdot p \cdot q + N \cdot (p+1) \cdot (q+1)-N\cdot \sigma (N)] / [N + \sigma (N) -1].
\end {equation}
Multiplying through by $N +\sigma (N) -1$ and simplifying, we get 
\begin {equation}\notag
[\sigma (N) -1] \cdot (p+1) \cdot (q+1) = \sigma (N) \cdot p \cdot q - N \cdot \sigma (N)
\end {equation} or
\begin {equation}\notag
\sigma (N) -1 + N \cdot \sigma (N) = p \cdot q - [\sigma (N) -1] \cdot p - [\sigma (N) -1] \cdot q.
\end {equation}
Adding $[\sigma (N) -1]^2$ to both sides and simplifying, we obtain
\begin {equation}\tag*{(3)}
\sigma (N) \cdot [N + \sigma (N) -1] = [p - \sigma (N) +1] \cdot [q- \sigma (N) +1].
\end {equation}
This condition is necessary and sufficient for $E \cdot p \cdot q$ and $E \cdot N \cdot r$ to be amicable.

To find the amicable pairs generated in this manner, all we need to do is obtain all the possible factorizations 
into pairs of the
left-hand side of (3), and for each such factorization $A \cdot B$, set $p-\sigma (N) +1 = A$ and $q- \sigma (N) +1 = B$
and solve for $p$ and $q$. When $p,\ q$ and $r = (p+1) \cdot (q+1) /\sigma (N) -1$ are all prime, we obtain an 
amicable pair. We give two examples:

\emph {Example 1.} $2^4 \cdot 23 \cdot 47$ and $2^4 \cdot 1151$ are amicable and satisfy equation (1). Then
equation (3) becomes
\begin {equation}\notag
2^{10} \cdot 3^4 \cdot 31 = (p-1151) \cdot (q-1151).
\end {equation}
Trying out the various possible factorizations into pairs of the left-hand side, and checking that $p,\ q$ and
$r = (p+1) \cdot (q+1) / 1152 -1 $ are prime, we get the two solutions 
\begin {equation}\notag
(p =1399,\  q = 11519,\  r = 13999)
\end {equation}
and 
\begin {equation}\notag
(p = 1583, \ q = 7103, \ r = 9767).
\end {equation}
Here the given amicable pair generates two amicable pairs. These are 
\begin {equation} \notag
(2^4 \cdot 23 \cdot 47 \cdot 13999, \ 2^4 \cdot 1399 \cdot 11519) 
\end {equation}
and
\begin {equation}\notag
(2^4 \cdot 23 \cdot 47 \cdot 9767, \ 2^4 \cdot 1583 \cdot 7103).
\end {equation}

\emph {Example 2.} $2^4 \cdot 19 \cdot 79$ and $2^4 \cdot 1599$ are not amicable, but satisfy condition (1).
Then equation (3) becomes
\begin {equation}\notag
2^8 \cdot 5^4\cdot 31 = (p-1599) \cdot (q-1599).
\end {equation}

Trying out the various possible factorizations into pairs of the left-hand side, and checking that 
$p,\ q$ and $r$ = $(p+1) \cdot (q+1) /1600 -1$ are prime, we get the single solution $(p =2591,\ q=6599,
\ r = 10691)$. Here the given non-amicable pair generates one amicable pair. This is $(2^4 \cdot 19 \cdot 79
\cdot 10691$, $2^4 \cdot 2591 \cdot 6599)$.


The selection of a suitable common factor $E$ was useful in obtaining our million amicable pairs. The equation
$\sigma (E) / E$ = a fraction $a/b$, has no solution for most fractions, but solutions do exist. In the case of
an amicable pair, $\sigma (E) /E$ must be a fraction between 1 and 2. When a solution exists, it is usually
the only solution. However, sometimes two or more solutions exist for the equation. There is one case which
gives seven solutions, namely $\sigma (E) /E = 1024/513$. Here the solutions are $E =$

\begin {tabular} {l l l l}
(1) & $3^3 \cdot 5^2 \cdot 19 \cdot 31$ & \qquad(2) & $3^4 \cdot 7 \cdot 11^2 \cdot 19^2 \cdot 127$ \\
(3) & $3^4 \cdot 7 \cdot 11^2 \cdot 19^4 \cdot 151 \cdot 911$ &\qquad (4) & $3^5 \cdot 7^2 \cdot 13 \cdot 19^2 \cdot 127$\\
(5) & $3^5 \cdot 7^2 \cdot 13 \cdot 19^4 \cdot 151 \cdot 911$ &\qquad (6) & $3^6 \cdot 5 \cdot 19 \cdot 23 \cdot 137\cdot 
547 \cdot 1093$\\
\end {tabular}
\begin {center}
(7) \ \ $3^{10} \cdot 5 \cdot 19 \cdot 23 \cdot 107 \cdot 3851$
\end {center}

The author made full use of this particular set, choosing as a common factor one of these, often multiplied
by a suitable factor. Each new amicable pair obtained yielded seven amicable pairs in most cases (on occasions
only six because of conflicts that may arise with the factors). There was one particular combination of $E$ and
$N$ that produced $7\times 35279 = 246953$ new amicable pairs. This was the case where
\begin {equation}\notag
E = 3^3 \cdot 5 ^2\cdot 19 \cdot 31 \cdot 757\cdot 3329 \ \text{and}
\ N = 1511 \cdot 72350721629 \cdot 2077116867246979.
\end {equation}

As an illustration, one of the solutions obtained is $(E\cdot N \cdot r, 
\  E \cdot p \cdot q)$ with $E$ and $N$ as indicated and
 $p =
227224727233807931924514243037$,\\
$q=1106480768793484882749455521321726608815428799,$\\
$r=1106480768793485337048629081543700341065155037$.
When multipled out, each member of this amicable pair has 87 digits.
The reader may view this and other examples by examining Pedersen's list
of known amicable pairs \cite {Pedersen95}.


The author's findings bring to more than two million the total number of known amicable pairs and strengthen the validity
of the as yet unproved conjecture that there are infinitely many amicable pairs.

%\section{Acknowledgements}

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

\bibitem{BH86}
W.~Borho and H.~Hoffmann, \emph{Breeding Amicable Numbers in Abundance}, Math. Comp. 46 (1986),
281-293. MR 87c:11003

%\bibitem{Colstello91}
%P.~Costello, \emph {Amicable pairs of the Form $(i,1)$}, Math. Comp. 56 (1991), 859-865.
%MR91K:11009

%\bibitem {Escott46}
%E.~B.~Escott, \emph {Amicable Numbers}, Scripta Math. 12 (1946), 61-72. MR8 135a

\bibitem {Euler50}
L.~Euler, \emph{De numeris amicabilibus}, Opuscula varii argumenti (1750), 23-107.

\bibitem {Lee68}
E.~J.~Lee, \emph {Amicable numbers and the bilinear Diophantine equation}, Math. Comp. 22 (1968), 181-187 MR 37 \#142.

\bibitem {LM72}
E.~J.~Lee and J.~S.~Madachy, \emph{ The History and Discovery of Amicable Numbers}, J.
Recr. Math. 5 (1972), Part 1, 77-93, Part 2, 153-173, Part 3, 231-249. MR 56\#5165a-e

\bibitem {te Riele86}
H.~J.~J.~te Riele, \emph {Computation of all the amicable pairs below $10^{10}$} Math. Comp. 47 (1986), 
361-368,S9-S40. MR 87i:11014

\bibitem {te Riele84}
H.~J.~J.~te Riele, \emph {On generating new amicable pairs from given amicable pairs}, 
Math. Comp. 42 (1984), 219-223. MR 85d:11107

\bibitem {RBBHL86}
H.~J.~J.~te Riele, W.~Borho, S.~Battiato, H.~Hoffmann, and E.~J.~Lee, \emph {Table of amicable pairs between
$10^{10}$ and $10^{52}$} (1986), Technical Report NM-N8603, Centrum voor Wiskunde en Informatica, Kruislaan 413, 
1098 SJ Amsterdam, the Netherlands

\bibitem {Pedersen01}
J.~Pedersen, \emph {Message from Jan Munch Pederson to the NMBRTHRY LIST on the Internet, January 30, 2001}.

\bibitem {Pedersen95}
J.~Pedersen,\emph {Known amicable pairs,}\\
http://www.vejlehs.dk/staff/jmp/aliquot/knwnap.htm


\end {thebibliography}


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

\vspace*{+.1in}
\noindent
{\small
(The amicable numbers are given in sequences
\htmladdnormallink{A002025}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002025},
\htmladdnormallink{A002046}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002046} and
\htmladdnormallink{A063990}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A063990}.)
}

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

\vspace*{+.1in}
\noindent
Received June 5, 2001; revised version received Nov 14, 2001.
Published in Journal of Integer Sequences, Feb 7, 2002.

\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}


.