![Archimedes_cattle_problem](https://upload.wikimedia.org/wikipedia/commons/b/b1/Archimedes_cattle_problem.svg)
Archimedes's cattle problem (or the or ) is a problem in
Diophantine analysis
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
, the study of
polynomial equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form
:P = 0
where ''P'' is a polynomial with coefficients in some field (mathematics), field, often the field of the rational numbers. For many authors, the term '' ...
s with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
solutions. Attributed to
Archimedes, the problem involves computing the number of cattle in a herd of
the sun god from a given set of restrictions. The problem was discovered by
Gotthold Ephraim Lessing in a Greek manuscript containing a poem of 44 lines, in the
Herzog August Library
The Herzog August Library (german: link=no, Herzog August Bibliothek — "HAB"), in Wolfenbüttel, Lower Saxony, known also as ''Bibliotheca Augusta'', is a library of international importance for its collection from the Middle Ages and ear ...
in
Wolfenbüttel
Wolfenbüttel (; nds, Wulfenbüddel) is a town in Lower Saxony, Germany, the administrative capital of Wolfenbüttel District. It is best known as the location of the internationally renowned Herzog August Library and for having the largest ...
,
Germany
Germany,, officially the Federal Republic of Germany, is a country in Central Europe. It is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
in 1773.
The problem remained unsolved for a number of years, due partly to the difficulty of computing the huge numbers involved in the solution. The general solution was found in 1880 by (1845–1916), headmaster of the ' (
Gymnasium of the Holy Cross) in Dresden, Germany. Using
logarithmic tables, he calculated the first digits of the smallest solution, showing that it is about
cattle, far more than could fit in the
observable universe
The observable universe is a ball-shaped region of the universe comprising all matter that can be observed from Earth or its space-based telescopes and exploratory probes at the present time, because the electromagnetic radiation from these ob ...
.
The decimal form is too long for humans to calculate exactly, but
multiple-precision arithmetic
In computing, an arithmetic logic unit (ALU) is a combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numb ...
packages on computers can write it out explicitly.
History
In 1769,
Gotthold Ephraim Lessing was appointed librarian of the Herzog August Library in
Wolfenbüttel
Wolfenbüttel (; nds, Wulfenbüddel) is a town in Lower Saxony, Germany, the administrative capital of Wolfenbüttel District. It is best known as the location of the internationally renowned Herzog August Library and for having the largest ...
, Germany, which contained many Greek and Latin manuscripts.
A few years later, Lessing published translations of some of the manuscripts with commentaries. Among them was a Greek poem of forty-four lines, containing an arithmetical problem which asks the reader to find the number of cattle in
the herd of the god of the sun. It is now generally credited to Archimedes.
Problem
The problem, as translated into English by Ivor Thomas, states:
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, divided into four herds of different colours, one milk white, another a glossy black, a 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 of 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 a 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 cattle 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 none 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.
Solution
The first part of the problem can be solved readily by setting up a
system of equations. If the number of white, black, dappled, and yellow bulls are written as
and
, and the number of white, black, dappled, and yellow cows are written as
and
, the problem is simply to find a solution to
:
which is a system of seven equations with eight unknowns. It is
indeterminate and has infinitely many solutions. The least positive integers satisfying the seven equations are
:
which is a total of cattle,
and the other solutions are integral multiples of these. Note that given the
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
then the first four numbers are multiples of ''p'', and both ''p'' and ''p+1'' will appear repeatedly below.
The second part of the problem states that
is a
square number
In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals and can be written as .
The usu ...
, and
is a
triangular number
A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots i ...
. The general solution to this part of the problem was first found by A. Amthor in 1880. The following version of it was described by
H. W. Lenstra,
based on
Pell's equation
Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinates, ...
: the solution given above for the first part of the problem should be multiplied by
:
where ''j'' is any positive integer and
:
Equivalently, squaring ''w'' results in
:
where
is the fundamental solution of the
Pell equation
Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinates, ...
:
The size of the smallest herd that could satisfy both the first and second parts of the problem is then given by ''j'' = 1 and is about
(first solved by Amthor). Modern computers can easily print out all digits of the answer. This was first done at the
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario, Canada. The main campus is on of land adjacent to "Uptown" Waterloo and Waterloo Park. The university also operates ...
, in 1965 by
Hugh C. Williams, R. A. German, and Charles Robert Zarnke. They used a combination of the
IBM 7040
The IBM 7040 was a historic but short-lived model of transistor computer built in the 1960s.
History
It was announced by IBM in December 1961, but did not ship until April 1963. A later member of the IBM 700/7000 series of scientific computers ...
and
IBM 1620
The IBM 1620 was announced by IBM on October 21, 1959, and marketed as an inexpensive scientific computer. After a total production of about two thousand machines, it was withdrawn on November 19, 1970. Modified versions of the 1620 were used as ...
computers.
[ (includes pictures)]
Pell equation
The constraints of the second part of the problem are straightforward and the actual
Pell equation
Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinates, ...
that needs to be solved can easily be given. First, it one asks that ''B'' + ''W'' should be a
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
, or using the values given above,
:
thus one should set ''k'' = (3)(11)(29)(4657)''q''
2 for some integer ''q''. That solves the first condition. For the second, it requires that ''D'' + ''Y'' should be a
triangular number
A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots i ...
:
:
Solving for ''t'',
:
Substituting the value of ''D'' + ''Y'' and ''k'' and finding a value of ''q''
2 such that the
discriminant of this quadratic is a perfect square ''p''
2 entails solving the
Pell equation
Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinates, ...
:
Amthor's approach discussed in the previous section was essentially to find the smallest
such that it is integrally divisible by
. The fundamental solution of this equation has more than 100,000 decimal digits.
References
Further reading
*
*
*
*
*
External links
*—Complete decimal solution to the second problem
*
{{Archimedes
Diophantine equations
Large integers
Works by Archimedes
Cattle in literature