\documentstyle{article}
\renewcommand{\baselinestretch}{1.3}
\newcommand{\itemspace}{\hspace{8pt}}
\newcommand{\hfhf}{\left(\frac{1}{2},\frac{1}{2}\right)}
\newcommand{\overp}{\overline{P}}
\def\thefigure{\arabic{section}.\arabic{subsection}.\arabic{figure}[p]}
\def\mod{{\rm mod}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%% Welcome to the macros of Ilan Vardi!
%%%
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%
%%%%%% 1 in margins produced by this
%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.9in}
\setlength{\topmargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%% TeX's eqalign macros....
%%%
\catcode`@=11
\newskip\@centering \@centering=0pt plus 1000pt minus 1000pt
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
\advance\baselineskip\dimen@
\advance\lineskiplimit\dimen@}
\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\newif\ifdt@p
\def\displ@y{\global\dt@ptrue\openup\jot\m@th
\everycr{\noalign{\ifdt@p \global\dt@pfalse
\vskip-\lineskiplimit \vskip\normallineskiplimit
\else \penalty\interdisplaylinepenalty \fi}}}
\def\@lign{\tabskip\z@skip\everycr{}} % restore inside \displ@y
\def\displaylines#1{\displ@y
\halign{\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}\crcr
#1\crcr}}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
&$\@lign\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$\@lign##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
&$\@lign\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$\@lign##$}\tabskip\displaywidth\crcr
#1\crcr}}
\catcode`@=12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% boxed text
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newlength{\boxedparwidth}
\setlength{\boxedparwidth}{.92 \textwidth}
\newenvironment{boxedtext}
{\begin{center}
\begin{tabular}{|@{\hspace{.15 in}}c@{\hspace{.15 in}}|}
\hline \\ \begin{minipage}[t]{\boxedparwidth}
\setlength{\parindent}{.25 in}}
{\end{minipage} \\ \\ \hline \end{tabular} \end{center}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\calc{{\cal C}}
\begin{document}
\begin{center}
{\Large Archimedes' Cattle Problem}
\bigskip
{ Ilan Vardi}
\end{center}
\begin{quotation}
\begin{center}
{\large A Problem}
\end{center}
\bigskip\smallskip\noindent
which Archimedes devised
%\footnote{The actual word in the
%translation is ``solved'', but D.H.~Fowler notes that ``devised'' is
%more appropriate \cite{Fowler}.}
in epigrams, and which
he communicated to students of such matters at Alexandria in a letter
to Eratosthenes of Cyrene.
\smallskip
If thou art diligent and wise, O stranger, compute the number of
cattle of the Sun, who once upon a time grazed on the fields of the
Thrinacian isle of Sicily,
%\footnote{This seems to be a reference to
%the twelfth book of Homer's Odyssey where the lines: `Then you will
%coast Thrin\' akia, the island where H\^elios' cattle graze, fine
%herds, and flocks of goodly sheep. The herds and flocks are seven,
%with fifty beasts in each.' \cite[Book 12, line 95??]{Odyssey}.
%Note that Archimedes lived on the Island of Sicily.}
divided into four herds of different colours, one milk white, another
glossy black, the third yellow and the last dappled. In each herd were
bulls, mighty in number according to these proportions: Understand,
stranger, that the white bulls were equal to a half and a third of the
black together with the whole of the yellow, while the black were
equal to the fourth part of the dappled and a fifth, together with,
once more, the whole of the yellow. Observe further that the remaining
bulls, the dappled, were equal to a sixth part of the white and a
seventh, together with all the yellow. These were the proportions of
the cows: The white were precisely equal to the third part and a
fourth of the whole herd of the black; while the black were equal to
the fourth part once more of the dappled and with it a fifth part,
when all, including the bulls, went to pasture together. Now the
dappled in four parts were equal in number to a fifth part and a sixth
of the yellow herd. Finally the yellow were in number equal to a sixth
part and seventh of the white herd.
If thou canst accurately tell, O stranger, the number of Cattle of the
Sun, giving separately the number of well-fed bulls and again the
number of females according to each colour, thou wouldst not be called
unskilled or ignorant of numbers, but not yet shalt thou be numbered
among the wise.
But come, understand also all these conditions regarding the cows of
the Sun. When the white bulls mingled their number with the black,
they stood firm, equal in depth and breadth, and the plains of
Thrinacia, stretching far in all ways, were filled with their
multitude. Again, when the yellow and the dappled bulls were gathered
into one herd they stood in such a manner that their number, beginning
from one, grew slowly greater till it completed a triangular figure,
there being no bulls of other colours in their midst nor one of them
lacking.
If thou art able, O stranger, to find out all these things and gather
them together in your mind, giving all the relations, thou shalt
depart crowned with glory and knowing that thou hast been adjudged
perfect in this species of wisdom.
\end{quotation}
This problem, in the form of 22 elegiac couplets, was discovered in
modern times by the German critic and dramatist G.E.~Lessing who found
it in the library of Wolfenb\"uttel, Northern Germany, where he was
librarian. In 1773 he published the problem along with a scholium
containing an incorrect solution \cite[p.~100]{Lessing} (see
\cite[Vol.~3, p.~171]{Mugler} for the scholium and its French
translation). The translation used here is from \cite[p.~202]{Loeb},
where,
following D.H.~Fowler \cite{Fowler}, the word ``devised'' has been
used instead of ``solved.''
\medskip
The problem is surprisingly difficult and it was not solved until a
hundred years ago by Amthor \cite{Amthor}, who showed that the complete
solution consists of eight numbers each having about $206,545$
digits. The simple nature of the question and the difficulty of its
solution makes this a perfect example of a challenge problem and shows
once more that Archimedes is one of the greatest mathematicians of all
time.
Naturally, Amthor did not write out the solution;
he gave only the
first four significant digits. Many accounts of the solution are
based on Amthor's paper, e.g., \cite{Heath}, where reduction to a
Pell equation is described. Several subsequent
papers give detailed derivations of the solution \cite{Grosjean91}.
The aim of this paper is to take the Cattle Problem out of the realm
of the ``astronomical'' and put it into manageable form. This is
achieved in formulas (12) and (13) which give explicit forms for the
solution. For example, the smallest possible value for the total
number of cattle satisfying the conditions of the problem is
$$
\left\lceil{\scriptstyle \frac{25194541}{184119152}}\, ({\scriptstyle
109931986732829734979866232821433543901088049 +
50549485234315033074477819735540408986340 \sqrt{4729494}})^{4658}
\right\rceil,
$$
where $\lceil x\rceil$ is the smallest integer $\ge x$.
This formula is an analog of the formula expressing
the $n$th Fibonacci number as the closest integer to
$\left((1+\sqrt{5})/2\right)^n/\sqrt{5}$.
The actual digits of the above number written out take up 47 pages in
\cite{Nelson2}.
Regarding the computation of the digits of a solution to the Cattle
Problem, D.H.~Fowler \cite{Fowler} comments: ``I don't know what
anybody would do with a solution, once found, except use it as a piece
of mathematical wall--paper!''
I also show how the Cattle Problem leads to a relatively small
solution by using classical formulas of analytic number theory. These
results allow one to compare the size of solutions to different Pell
equations, and I give an example of another Pell equation with
smaller coefficients, but whose smallest solution has over 30 million
digits (150 times more than the cattle problem).
Apart from this last result, the methods used depend only on
some basic results of number theory and the elementary theory of
finite fields. The analysis is simplified by good
notation and the use of computer algebra systems ({\sl Mathematica\/}
and Pari) that permit some cumbersome computations to be reduced to a
single computer command. The method presented here is easily amenable
to computer computation (see \cite{Vardi2} for details) and the reader
can use Section~2.6 to generate a computer solution in a few hours.
\subsection*{1. The solution, part I}
\noindent
{\bf 1.1. An algebraic formulation.}
To solve the Cattle Problem, one considers it algebraically by writing
$W,w$ for the white bulls and cows, respectively, and similarly, $X,x,
Y, y, Z,z$ for the number of black, yellow, and dappled bulls and
cows. The first set of relations is
%$$
%\pmatrix{W\cr X\cr Z\cr w\cr x\cr y\cr z\cr} =
%\pmatrix{0 & \frac{1}{2} + \frac{1}{3} & 1 & 0 &0 &0 &0 &0\cr
% 0 & 0 & 1 & \frac{1}{4} + \frac{1}{5} & 0 & 0 & 0 & 0\cr
% \frac{1}{6}+\frac{1}{7} & 0 & 1 & 0 & 0 & 0 & 0 & 0\cr
% 0 & \frac{1}{3} +\frac{1}{4} & 0 & 0 & 0 &\frac{1}{3} + \frac{1}{4}&0&0\cr
% 0 & 0 & 0 & \frac{1}{4} + \frac{1}{5}&0&0&0&\frac{1}{4} + \frac{1}{5}\cr
% \frac{1}{6} + \frac{1}{7}&0&0&0&\frac{1}{6} + \frac{1}{7}&0&0&0\cr
% 0&0&\frac{1}{5} + \frac{1}{6}&0&0&0&\frac{1}{5} + \frac{1}{6}&0\cr
%}
%\, \pmatrix{W\cr X\cr Y\cr Z\cr w\cr x\cr y\cr z\cr} \,.
%\leqno(1)
$$
\eqalign{
&W = \left(\frac{1}{2} + \frac{1}{3}\right) X + Y\,,
\quad
X = \left(\frac{1}{4} + \frac{1}{5}\right) Z + Y\,,
\quad
Z = \left(\frac{1}{6} + \frac{1}{7}\right) W + Y\,,
\cr\noalign{\vskip 5pt}
&w = \left(\frac{1}{3} + \frac{1}{4}\right)( X + x)\,,
\quad
x = \left(\frac{1}{4} + \frac{1}{5}\right)(Z + z)\,,
\quad
y = \left(\frac{1}{6} + \frac{1}{7}\right)(W + w)\,,
\quad
z = \left(\frac{1}{5} + \frac{1}{6}\right)( Y + y)\,.
\cr
}
\leqno(1)
$$
The additional relations are
$$
\leqalignno{
W + X &= \;\mbox{a square,}
&(2)
\cr\noalign{\vskip 10pt}
&&{\rm and}
\cr\noalign{\vskip 10pt}
Y + Z &= \;\mbox{a triangular number,}
&(3)
\cr
}
$$
where a triangular number has the form
$1 + 2 + 3 + \cdots + n=n(n+1)/2$.
\bigskip
The first part of the problem is quite easy--its solution is
essentially what appears in the scholium, so it is the second part
which makes the problem a difficult one. As a preliminary exercise,
the reader can try solving a simple analog of the second part
\smallskip\noindent
{\bf Problem:} In the game of pool one is given balls arranged in a
square tray, but when one ball is used as the cue ball, the others can
be racked in a triangle. How many balls are there?
\bigskip\noindent
{\bf 1.2 Solving the linear system.}
The linear system of equations (1) is easily solved (e.g.,
with {\sl
Mathematica'}s {\tt Solve} command). Letting
$
{\bf S} = (W, X, Y, Z, w, x, y , z)
$
denote a solution, one gets a one dimensional space of solutions
parametrized by $W$
$$
{\bf S}
=
\left(1,
\frac{267}{371} , \frac{297}{742} ,
\frac{790}{1113} , \frac{171580}{246821} ,
\frac{815541}{1727747} , \frac{1813071}{3455494} ,
\frac{83710}{246821} \right) W\,.
$$
Since you can't have fractional cattle, the solution has to be
in integers, which you get by multiplying by the least
common multiple of the denominators on the right (once again
a single {\sl Mathematica\/} command {\tt LCM} does the trick).
This number turns out to be $10366482$ and
multiplying through gives
the general integer solution to the seven equations
$$
{\bf S} =
(10366482, 7460514, 4149387,7358060,
7206360, 4893246, 5439213 ,3515820) \, n\,,
\ \, {\rm for}\ \, n=1,2,\ldots.
\leqno(4)
$$
The solution given in the scholium corresponds to $n=80$.
\bigskip\noindent {\bf 1.3. Wurm's problem.}
Actually, the
language of the Cattle Problem leaves some ambiguity as to whether
equation (2) refers to a square {\sl number\/} of bulls or whether
they form a square figure, since bulls are longer than they are wide.
The latter problem simply requires that $W + X$ be a ``rectangular''
number, i.e., a nonprime. Since this amounts to ignoring condition
(2), its solution is much simpler and was solved by J.F.
Wurm \cite{Wurm}, so is called {\sl Wurm's problem\/} while the
former is called the {\sl complete problem.}
To solve Wurm's problem,
one needs to find a value of $n$ for which (3) is satisfied, i.e., $Y
+ Z = q(q+1)/2$, and for which $W+X$ can be written as a product of
two numbers whose ratio is roughly that of a bull. Using (4)
$Y + Z = (4149387 + 7358060) n = 11507447 n$, so this can be
rewritten as $11507447 n = q(q+1)/2$, or $q^2 + q - 2 \cdot 11507447 n
= 0$. Since $q$ must be an integer, one is looking for $n$ such that
this quadratic has an integer solution, i.e., $\sqrt{1 + 4 (2 \cdot
11507447 n)}$ is an integer. Thus, a solution exists exactly
when $1 + 92059576 n$ is a perfect square. This can be written as
$x^2 = 1 + 92059576n$ for some $n$. Another way to state this is to
find $x$ for which
$$
x^2 \equiv 1\; ({\rm mod}\, 92059576)\,.
\leqno(5)
$$
To solve this equation, one uses the Chinese Remainder Theorem,
which says that a solution of (5) exists for each combination
of solutions of
$$
x^2 \equiv 1\; ({\rm mod}\, d)
\leqno(6)
$$
where $d$ is a prime power factor of
$92059576 = 2^3\cdot 7\cdot 353 \cdot 4657$.
The solutions to (6) are given by
$x = 1, 3, 5, 7\; {\rm mod}\, 8$ and
$x = \pm 1\; {\rm mod }\, d$ for $d = 7$, $353$, and $4657$.
The solutions ${\rm mod}\, 92059576$ are built up from
these. This can be done using {\sl Mathematica'}s
implementation of the Chinese Remainder Theorem
algorithm. The complete list of solutions that are greater than 1 is
$$
\eqalign{
& 3287843, 4303069, 7590911, 15423983,
18711825, 19727051, 23014893, 23014895,
\cr &
26302737, 27317963, 30605805, 38438877,
41726719, 42741945, 46029787, 46029789,
\cr &
49317631, 50332857, 53620699, 61453771,
64741613, 65756839, 69044681, 69044683,
\cr &
72332525, 73347751, 76635593, 84468665,
87756507, 88771733, 92059575\,.
\cr
}
$$
Each of these generates a family of solutions;
the smallest being $3287843$. The corresponding value of $n$ is
$$
(3287843^2 - 1)/92059576 = 117423\,.
$$
Letting $n = 117423$ in (4) yields the solution
$$
\eqalign{
&(1217263415886, 876035935422, 487233469701, 864005479380,
\cr\noalign{\vskip 5pt}
&\quad 846192410280, 574579625058, 638688708099,
412838131860)\,,
\cr
}
$$
and the total number of cattle is $5916837175686$.
To check conditions (2) and (3) note that
$$
W + X = 2093299351308 = 2^2\cdot 3^4 \cdot 11\cdot 29\cdot 4349 \cdot 4657\,,
$$
is not prime (the closest representation to a square
is $W + X = 1409076 \cdot 1485583$). Moreover,
$Y + Z = 487233469701 + 86400547938=573634017639$, and
the equation $q^2 + q - 2 \cdot 573634017639 = 0$ has the positive
solution $q = 1643921$, so
$$
Y + Z = \frac{1643921 (1643921 + 1)}{2}\,,
$$
as required.
\subsection*{2. The solution, part II}
\noindent
{\bf 2.1. Reduction to the Pell equation.}
The solution to the complete problem requires satisfying the
extra condition that $W + X$ is a square. From (4), one has
$$
W + X = (10366482 + 7460514) n = 17826996 n\,.
$$
One can get information about $n$ by looking at the factorization
$17826996 = 2^2 \cdot 3 \cdot 11 \cdot 29\cdot 4657$,
which shows that $2^2 \cdot 3 \cdot 11 \cdot 29\cdot 4657\, n$ is a square
and thus
$$
n = 3 \cdot 11\cdot 29 \cdot 4657 \, m^2
= 4456749 m^2\,.
$$
for some integer $m$. Inserting this in (4) gives
$$
\eqalign{
{\bf S} &=
(46200808287018, 33249638308986,
18492776362863, 32793026546940,
\cr\noalign{\vskip 3pt}
& \qquad 32116937723640, 21807969217254,
24241207098537, 15669127269180)\, m^2 \,.
\cr
}
\leqno(7)
$$
As before,
$Y + Z$ must be a triangular number, i.e.,
$$
Y + Z = (18492776362863 + 32793026546940) m^2 =
51285802909803 m^2 = \frac{q(q+1)}{2}\,,
$$
so one solves $q^2 + q - 2\cdot 51285802909803 m^2 = 0$,
which has an integer solution
exactly when $1 + 4\cdot 2 \cdot 51285802909803 m^2 $ is a square, i.e.,
it has solution $(k-1)/2$ if
$$
1 + 410286423278424 m^2 = k^2\,,
\leqno(8)
$$
for some $k$. Equation (8) is the well--known
{\sl Pell's equation\/} from number theory \cite{Niven}.
If we factor
$$
410286423278424
=
2^3\cdot 3 \cdot 7 \cdot 11\cdot 29\cdot 353\cdot 4657^2\,,
$$
(8) can be written as
$
1 + 2\cdot 3 \cdot 7\cdot 11 \cdot 29\cdot 353 (2\cdot 4657 m)^2 = k^2
$
which, upon noting that
$4729494 = 2 \cdot 3 \cdot 7 \cdot 11 \cdot 29 \cdot 353$,
is equivalent to
$$
k^2 - 4729494 \ell^2 =1\,,
\leqno(9)
$$
where $\ell$ is divisible by 2 and by 4657.
\smallskip\noindent {\bf Remarks:} According to the analysis of
Section~3.9, one should actually look at the equation\\ $ x^2 -
4\cdot 4729494\, y^2 = 4\,. $ This equation is equivalent to (9)
since $x$ must be an even number, so dividing by 4 gives
$(x/2)^2 - 4729494\, y^2 = 1$,
which is the same as (9).
\medskip\noindent
The reader should have similarly
reduced the Pool Problem to the equation $x^2 -
2 y^2 = -7$, which is solved by finding its minimal solutions
and combining them with solutions to the Pell equation $u^2 - 2v^2 = 1$.
\newpage
\bigskip\noindent
{\bf 2.2. Solution of Pell's equation using continued fractions.}
It is known \cite[Chapter~9]{Fowler} \cite[Section~4.5.3]{Knuth}
that every real number can be expanded as a continued fraction.
For example
$$
\eqalign{
\pi &= 3.141592653\ldots = 3 + .141592653\ldots
\cr\noalign{\vskip 5pt}
& = 3 + \frac{1}{7.062513305\ldots} = 3 + \frac{1}{7 + .062513305\ldots}
\cr\noalign{\vskip 5pt}
&= 3 + \frac{1}{7 +\displaystyle\frac{1}{15.99659440\ldots}}
= 3 + \frac{1}{7 +\displaystyle\frac{1}{15 + .99659440\ldots}}
\cr\noalign{\vskip 5pt}
&=3 + \frac{1}{7 +\displaystyle\frac{1}{15 +
\displaystyle \frac{1}{1.003417231\ldots}}}
=
3 + \frac{1}{7 +\displaystyle\frac{1}{15 +
\displaystyle\frac{1}{1 + .003417231\ldots}}}
\cr\noalign{\vskip 5pt}
& = 3 + \frac{1}{7 +\displaystyle\frac{1}{15 +
\displaystyle\frac{1}{1 + \displaystyle\frac{1}{292.63459088\ldots}}}}
=3 + \frac{1}{7 +\displaystyle\frac{1}{15 +
\displaystyle\frac{1}{1 + \displaystyle\frac{1}
{\matrix{292 &+&\cr && \ddots}}}}}
\cr
}
$$
which is conventionally written, for typographical convenience, as
$\pi = [3, 7, 15, 1, 292, \ldots]$. A representation of this type
terminates only if the number is rational.
Good approximations occur when one truncates the expansion, especially
just before a large coefficient. For example,
$\pi \approx [3, 7] = 3 + 1/7 = 22/7$, and a much better
approximation is given by $[3, 7, 15, 1] = 355/113$. In fact, it can be
shown that such truncations give {\sl optimal\/} approximations
in the following sense: if $p/q$ is an approximation from truncation
then $p'/q'$ is a poorer approximation for any $1 \le q'