Archimedes' cattle problem

from Wikipedia, the free encyclopedia

The Archimedes' cattle problem , even Problema bovinum , the attenuated version of an unsolvable problem in number theory from the theory Diophantine equations , that is of polynomial equations over the integers . The original problem is attributed to Archimedes : The number of cattle (bulls and cows, each with four types) in a herd of the sun god is to be determined from some constraints.

history

The bovine problem was in 1773 by Gotthold Lessing in a Greek manuscript of the Herzog August library in Wolfenbüttel discovered (Cod. Guelf. 77 Gud. Graec.) Having a in 44 couplets drafted letter of Archimedes to Eratosthenes of Cyrene contained (that is, from Syracuse by Alexandria ).

Πληθὺν Ἠελίοιο βοῶν, ὦ ξεῖνε, μέτρησον φροντίδ 'ἐπιστήσας, εἰ μετέχεις σοφίης, πόσση ἄρ' ἐν πεδίοις Σικελῆς ποτ 'ἐβόσκετο νήσου Θρινακίης τετραχῇ στίφεα δασσαμένη χροιὴν ἀλάσσοντα · τὸ μὲν λευκοῖο γάλακτος, κυανέῳ δ' ἕτερον χρώματι λαμπόμενον, ἄλλο γε μὲν ξανθόν, τὸ δὲ ποικίλον ... (The crowd of Helio's herd, my friend, measure ...) - strictly translated it is not about cattle.

Whether the letter is actually from Archimedes is doubted by Lessing and others, but the problem itself may be due to Archimedes due to its difficulty. An indication of this is Archimedes' interest in large numbers, such as the one that emerges in The Sand Calculator .

A philological version of the Greek text and a translation into Latin can be found in the second volume of the edition of Archimedes' works by Johan Ludvig Heiberg . A German translation of the poem was made and published by Georg Nesselmann (1842), another by Bernhard Krumbiegel (1880).

The text published by Lessing contains a partial solution which, however, ignores a line of the original text and does not meet two requirements from the second part of the poem. Even the weakened version without these additional requirements remained unsolved until a few years ago because of the calculation of very large numbers required for the solution. A solution method was found by August Amthor in 1880 , with which the solution of about 7.76 · 10 206544 cattle (a number with 206,545 digits) could be determined. The computers ( IBM 7040 and IBM 1620 ) developed by Hugh C. Williams , Gus German and Bob Zarnke in 1965 required a total computing time of 7 hours 49 minutes to calculate the explicit decimal representation .

problem

The problem, in a simplified version based on Nesselmann and Krumbiegel, which does not retain the meter:

Count, my friend, the cattle under the sun that once grazed under the Sicilian sun, divided into four herds according to their color. One is milk white, one black, one spotted and one yellow. The number of bulls of each color is greater than that of cows of that color (this is omitted in the modern version), and the relationship between them is as follows:

white bulls black bulls + yellow bulls,
black bulls spotted bulls + yellow bulls,
spotted bulls white bulls + yellow bulls,
white cows black herd,
black cows spotted herd,
spotted cows yellow herd,
yellow cows white herd.

If you, my friend, cannot tell me the number of cattle of every kind, bulls and cows, you cannot consider yourself highly qualified. But consider the following additional relationships between the bulls under the sun:

White bulls + black bulls = a square number,
Spotted bulls + yellow bulls = a triangular number .

When you have also calculated this, O friend, and you have found the total number of cattle, then rejoice as a conqueror because you have proven to yourself that you are a very talented calculator.

Formulated in the form of an equation: Find the numbers W, X, Y, Z of different colored bulls and w, x, y, z of cows in the corresponding colors with:

The total number of cattle is then .

In the more difficult form, the additional conditions are:

required (for whole numbers m, n). For the solution method, see also the article on Pell's equation .

Detailed solution of the first easier part of the task

If you transform the first three equations appropriately and remove the fractions, you get the following system of equations:

Three equations with four unknowns and usually have an infinite number of solutions, so the system of equations is underdetermined. An unknown is freely selectable. In this case , assuming the unknown is known, the following solutions are obtained:

But because and must be integers (after all, there is a certain number of cattle in question), must also be integers. So it must be a multiple of 891. So be with an integer . Then the following solutions are obtained:

If you consider the other four equations, remove the fractions and transform them appropriately, you get the following system of equations:

If you insert the results of the first system of equations, i.e. and , you get the following system of equations:

Since this is freely selectable, it is a clearly solvable system of equations with 4 equations and 4 unknowns and . The following solutions are obtained:

Again, and have to be integers, because we are dealing with the numbers of cattle. So it must be an integer. So it has to be a multiple of 4657. So be with an integer . Then you get the following solutions:

The first and easier part of the Archimedean cattle problem (without the two additional conditions) has the following solution ( any whole number can be chosen):

The number of white bulls is .

The number of black bulls is .

The number of spotted bulls is .

The number of yellow bulls is .

The number of white cows is .

The number of black cows is .

The number of spotted cows is .

The number of yellow cows is .

So the total number of cattle is .

Detailed smallest solution to the second, more difficult part of the task

Now to solve the more difficult second part of the problem:

If you put in for and for , you get

The prime factorization of . Thus one obtains the equation

So that the left part is a complete square, the following must apply:

with an integer .

Now consider the equation . Multiplied by 2 you get the equation . Put everything on one side and you get the equation

With the formula for solving quadratic equations with , and one obtains the following two solutions for :

The second solution can be seen as an uninteresting solution because the number of cattle should certainly be positive.

So only the first solution is of interest .

Because positive is supposed to be an integer, the root has to be omitted. This is only possible if the expression under the root, the so-called discriminant , is a complete square. So the following must apply:

with positive integer. is obviously odd, because the sum of an even and an odd number is certainly odd. But if it is odd, it must also be odd. Thus, an odd number reduced by 1 is even, and thus half of an even number and therefore is definitely a positive integer. So you have to only appropriate and thus a suitable find and the cattle problem is solved.

If one now substitutes the following intermediate results for and :

So one gets the equation:

This gives the following equation:

Because is, Pell's equation follows:

If you take the prime factorization into account, you get Pell's equation, which is somewhat easier to solve:

Because 4729494 is not a square number, this Pell equation has an infinite number of solutions.

It is solved with the continued fraction expansion of , which reads as follows with a period length of 92 and thus with a total length of 93:

Pell's equation above has the following smallest (minimal) solution:

However, it is not an integer and therefore the above minimal solution of Pell's equation is still not the sought-after solution to the cattle problem.

It must be a divisor of a certain (smallest possible) that has the number as a divisor.

When you have the minimum solution of Pell's equation above, you only have to use the following two iteration formulas, with which you get all further (infinitely many) solutions of Pell's equation (see Pell's equation , section "Generating further solutions based on a known one") :

with the above and .

The first iteration step is

Unfortunately, this also doesn't have the number as a divisor.

Also with the next, the second iteration step

one gets one that does not have the number as a divisor.

Only after an unbelievable 2329 iteration steps do you get the following smallest solution:

And so you get . This can also be used to calculate and use above at and .

The more difficult form of the Archimedean cattle problem (including the two additional conditions) thus has the following smallest solution:

The number of white bulls is .

The number of black bulls is .

The number of spotted bulls is .

The number of yellow bulls is .

The number of white cows is .

The number of black cows is .

The number of spotted cows is .

The number of yellow cows is .

So the total number of cattle is .

The exact results for the number of individual bulls and cows and for the total number of cattle, i.e. all 206544 and 206545 positions, can be found on a website.

The white bulls, of which there are pieces, and the black bulls, of which there are pieces, can be arranged in a square so that there are bulls on each side of the square .

The spotted bulls, of which there are pieces, and the yellow bulls, of which there are pieces, can be arranged in a triangle so that there are bulls on each side of the triangle .

All solutions to the second, more difficult part of the task

Pell's equation above , which was transformed into Pell's equation , of course has the same integral minimum solution already obtained above

.

This Pell equation has an infinite number of solutions. Each of these solutions is also a solution to the cattle problem. Thus the cattle problem also has an infinite number of solutions.

If you know the minimal solution of Pell's equation above, you have to apply the following two iterative formulas again, with which you get all other (infinitely many) solutions of Pell's equation:

The first iteration step is

with and .

In fact, and is the second smallest solution of Pell's equation .

With the next, the second iteration step

one obtains the third smallest solution of Pell's equation.

The general rule:

gives all pairs of solutions to Pell's equation .

But above all those are interesting . With that you can calculate again and start at and above . This is how you get all the other solutions to the cattle problem.

All the solutions to the second, more difficult part of the task - alternative formulas

If you want to know all the infinitely many solutions to this bovine problem, the following formulas, which the mathematician H. W. Lenstra Jr. published on, are also available.

Be

and

With

The smallest solution is the smallest solution of the cattle problem calculated above .

The difficult form of the Archimedean cattle problem (including the two additional conditions) has the following -smallest solution ( can be chosen as a positive whole number):

The number of white bulls is .

The number of black bulls is .

The number of spotted bulls is .

The number of yellow bulls is .

The number of white cows is .

The number of black cows is .

The number of spotted cows is .

The number of yellow cows is .

So the total number of cattle is .

Individual evidence

  1. a b Peter Schreiber: A Note on the Cattle Problem of Archimedes. ( Memento of December 3, 2013 in the Internet Archive ). (PDF; 131 kB). In: Historia Mathematica. 20, 1993, pp. 304-306.
  2. Gotthold Ephraim Lessing: On history and literature. From the treasures of the ducal library in Wolfenbüttel. Second post. Braunschweig 1773, pp. 421-446 .
  3. http://users.ntua.gr/dimour/greats/Archimedes/index.html
  4. Cf. among others Jacob Struve, Karl Ludwig Struve: Old Greek epigram of mathematical content, treated mathematically and critically. Altona 1821.
  5. See e.g. B. Bernhard Krumbiegel, August Amthor: The problema bovinum of Archimedes. In: Journal for mathematics and physics, historical-literary department. 25, 1880, pp. 121-136, 153-171.
  6. ^ Johan Ludvig Heiberg (Ed.): Archimedis opera omnia cum commentariis Eutocii. E codice Florentino recensuit, latine uertit notisque illustrauit. Vol. 2 (PDF; 13.3 MB). Teubner, Leipzig 1881, pp. 446–455.
  7. Georg Heinrich Ferdinand Nesselmann: Attempt at a critical history of algebra. Vol. 1: The algebra of the Greeks. Reimer, Berlin 1842. ND Minerva, Frankfurt 1969, p.  482 (protocol), 483 (lines 1-30), 486-487 (lines 31-44).
  8. ^ Hugh C. Williams, R. Angus German, C. Robert Zarnke: Solution of the cattle problem of Archimedes. In: Mathematics of Computation. 19, 1965, pp. 671-674.
  9. ^ Merriman, Mansfield: The Cattle Problem of Archimedes. In: Popular Science Monthly. 67, 1905, pp. 660-665.
  10. ^ Archimedes in the 21st Century: The Cattle Problem, Computer Output (2nd Part) [1]
  11. ^ HW Lenstra Jr .: All solutions to the cattle problem of Archimedes. P. 187 ( PDF).

swell

  • G. Nesselmann: The algebra of the Greeks. Reimer, Berlin 1842 (reprint: Minerva Verlag, Frankfurt am Main 1969, ISBN 3-86598-328-6 ).

Web links