Lucifer riddle

The Lucifer riddle (also known by other names) is a mathematical riddle from the field of number theory that was published by the mathematician Hans Freudenthal .

The riddle impressively demonstrates how simply formulated and generally appearing prerequisites can be the starting point for complex mathematical considerations and also provide a precise and unambiguous solution. It is therefore quite widespread as an exercise in mathematics training or as an intelligent prize puzzle.

The riddle

There are different versions of the puzzle that are identical in content and differ only in terms of text. A popular version that led to the name "Lucifer Riddle" goes something like this:

The famous mathematicians Carl Friedrich Gauß and Leonhard Euler end up in hell after their death. Lucifer promises you freedom if you guess the two whole numbers between 1 and 100 (ie in the range {2,3, ..., 99}) that he has thought up. He calls Gauss the product and Euler the sum of the two numbers; then the following dialogue develops between the mathematicians:

Gauss: "I don't know the two numbers."

Euler: "That was clear to me."

Gauss: "Now I know the two numbers."

Euler: "Then I know her now too."

Regardless of the question of whether Gauss and Euler escaped from Hell, the task is to determine the two starting numbers from this information alone.

When Freudenthal published this problem in 1969, it was formulated more simply and without naming people. Instead of the upper limit of the two searched numbers, which should not be the same, the upper limit of the sum was specified. This does not change anything in the solution.

The solution

The two numbers we are looking for are and , for both , Gauss knows the product of both numbers, Euler the sum . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 1<a,b<100}$ ${\displaystyle m=a\cdot b}$ ${\displaystyle s=a+b}$

• Gauss: "I don't know the two numbers."

Gauss first determines the prime factorization of . The numbers and he can determine immediately if one of the following cases occurs: ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle b}$

1. ${\displaystyle m}$can be broken down into exactly two prime factors: One factor is , the other (interchanging does not provide a fundamentally different solution, the number 1 was excluded in the prerequisites). ${\displaystyle a}$ ${\displaystyle b}$
2. One of the prime factors of is greater than 50 : This factor must already be one of the two numbers sought; any multiplication by another factor would exceed 100 . ${\displaystyle m}$
3. ${\displaystyle m}$consists of the third power of a prime number: The factor would then be exactly this prime number and would be . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a^{2}}$

Since Gauss does not yet know the numbers at this point in time, none of the three cases can exist; the prime factorization of yields at least three factors, all of which are less than 50 and not all equal. ${\displaystyle m}$

• Euler: "That was clear to me."

From the sum total , Euler sees that the above-mentioned cases definitely do not exist. This excludes the following values ​​for : ${\displaystyle s}$ ${\displaystyle s}$

1. ${\displaystyle s=198}$: The only decomposition is 99 + 99 , Gauss could clearly derive the solution from the product 9801 .
2. ${\displaystyle s=197}$: The only decomposition is 98 + 99 , Gauss can also clearly determine this case from the product 9702 .
3. ${\displaystyle 54<s<197}$: In this range, one of the two summands could be a prime number from 53 to 97 . For example, from Euler's point of view, there is the possibility that is what Gauss would certainly have come from and (or vice versa). ${\displaystyle s=55}$ ${\displaystyle m=2\cdot 53=106}$ ${\displaystyle a=2}$ ${\displaystyle b=53}$
4. ${\displaystyle s<55}$and precisely: According to Goldbach's conjecture , in this case the two summands could be prime numbers (and then necessarily less than 50 ). Goldbach's Hypothesis has not been proven for all even numbers, but the range has long been checked. ${\displaystyle s<55}$
5. ${\displaystyle s=p+2}$, where the prime number is (and ): These numbers allow the decomposition into the prime numbers 2 and . ${\displaystyle p}$ ${\displaystyle p<50}$ ${\displaystyle p}$
6. ${\displaystyle s=51}$: In this case a decomposition 17 + 34 is possible, which Gauss can uniquely derive from the product 578 = 17 · 17 · 2 ( 17 · 17 = 289> 100 is out of the question as a solution number).

The only possible values ​​for remain values ​​of the following set . At most, with these, Euler can be sure that Gauss will not be able to read the solution from the product immediately. (None of them belong to the third case mentioned above:. ) ${\displaystyle s}$ ${\displaystyle S:=\left\{11,17,23,27,29,35,37,41,47,53\right\}}$ ${\displaystyle m=a^{3},s=a^{2}+a}$

Since all values ​​are odd, it is already clear that one of the numbers and is even, the other is odd. Furthermore, and in each case are less than 53 . ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

• Gauss: "Now I know the two numbers."

Gauss can break down his product in several ways, but only one of them gives a sum in . Among all possible cases, the following special cases should be highlighted: ${\displaystyle S}$

1. ${\displaystyle m}$contains an odd prime factor and multiple times the factor : The odd factor is one solution number, the other is a power of two. In this case, this is the only division that results in an even and an odd number. ${\displaystyle 2}$
2. ${\displaystyle m}$contains (as one of at least three) a prime factor : This prime factor is then necessarily one of the solution numbers. Multiplying this by any other factor would give a value over . ${\displaystyle 29}$ ${\displaystyle 53}$

• Euler: "Then I know her now too."

Euler sees that his sum can only be decomposed in one way, which gives one of the above cases. The following values ​​for are ruled out, as Euler could not determine a clear solution in these cases: ${\displaystyle s}$

1. All values ​​from : These can be decomposed both as and as, i.e. twice according to the type special case 2 ${\displaystyle 35}$ ${\displaystyle 29+b}$ ${\displaystyle 31+b}$
2. ${\displaystyle 11}$: Decomposition 7 + 4 and 3 + 8 (both correspond to special case 1)
3. ${\displaystyle 23}$: Decomposition 19 + 4 and 7 + 16 (also twice special case 1)
4. ${\displaystyle 27}$: Decomposition 23 + 4 and 19 + 8 (again in both cases special case 1)
5. ${\displaystyle 29}$: Decomposition 13 + 16 and 17 + 12 (the first is special case 1, the second is clearly readable for Gauss from the product 17 · 3 · 2 · 2 , because the only other possible division 51 · 4 gives the sum 55 )

This leaves the value 17 . Is there actually one (and only one) decomposition of 17 that Gauss can uniquely identify as the solution? To do this, all possible decompositions must be checked:

• ${\displaystyle 17=3+14:m=3\cdot 14=2\cdot 21}$is not clearly solvable for Gauss, since 2 + 21 = 23 also in S.
• ${\displaystyle 17=5+12:m=5\cdot 12=20\cdot 3}$also not clear (20 + 3 = 23 in S)
• ${\displaystyle 17=7+10:m=7\cdot 10=2\cdot 35}$also, because of 37 in p
• ${\displaystyle 17=9+8:m=9\cdot 8=24\cdot 3}$also, because of 27 in p
• ${\displaystyle 17=11+6:m=11\cdot 6=2\cdot 33}$also, because of 35 in p
• ${\displaystyle 17=15+2:m=15\cdot 2=6\cdot 5}$also, because of 11 in p

There remains, therefore , and a solution that meets the above special case. 1 In fact, this is the only solution that meets all of the conditions. ${\displaystyle a=13}$ ${\displaystyle b=4}$

One way to understand the solution

Those who have problems understanding the purely mathematical solution should put themselves in the shoes of Gauss and Euler. After all, everyone got their number: Gauss the product 52 and Euler the sum 17. (This is not the way to solve the riddle, as stated above, but rather to make the solution understandable in connection with the dialogue just needs a little math [grade 6, for example] and a little bit of language logic.)

So:

Gauss receives the product 52 ; Euler the sum 17 .

First Gauss breaks down the number 52 into the possible pairs of factors:

52 = 4 * 13 and 52 = 2 * 26

Since there can only be these two pairs of numbers for the product, Gauss is actually very close to the solution here. But he could only guess the result, which of course is out of the question for a mathematician. But he also sees that Euler can only have received the sums 17 (4 + 13) or 28 (2 + 26). Gauss prepares the following two tables:

Table 1 for the sum 17:

Can be dismantled into	product	possible pairs of factors
2 + 15	30th	2 · 15/3 · 10/5 · 6
3 + 14	42	2 21/3 14/6 7
4 + 13	52	2 · 26/4 · 13
5 + 12	60	2 x 30/3 20/4 15/5 5 12/6 10
6 + 11	66	2 · 33/3 · 22/6 · 11
7 + 10	70	2 · 35/5 · 14/7 · 10
8 + 9	72	2 36/3 24/4 18/6 12/8 9

Table 2 for the sum 28:

Can be dismantled into	product	possible pairs of factors
2 + 26	52	2 · 26/4 · 13
3 + 25	75	3 · 25/5 · 15
4 + 24	96	2 48/3 32/4 24/6 16/8 12
5 + 23	115	5 23
6 + 22	132	2 · 66/3 · 44/4 · 33/6 · 22/11 · 12
7 + 21	147	3 · 49/7 · 21
8 + 20	160	2 x 80/4 x 40/5 x 32/8 x 20/10 x 16
9 + 19	171	3 57/9 19
10 + 18	180	2 · 90/3 · 60/4 · 45/5 · 36/6 · 30/9 · 20/10 · 18/12 · 15
11 + 17	187	11 17
12 + 16	192	2 96/3 64/4 48/6 32/8 24/12/16
13 + 15	195	3 65/5 39/13 15
14 + 14	196	2 · 98/4 · 49/7 · 28/14 · 14

The tables show that neither he (Gauss) nor Euler can clearly see the pair of numbers he is looking for; so he decides to tell Euler that he can't figure out the numbers. Of course, Euler also thought about it beforehand. Since he has received the number 17 as the sum of the two numbers to be guessed, he also makes table 1 . He sees that Gauss can only form products that can be formed from at least two pairs of factors.

So now it comes to the above dialogue:

Gauss: "I don't know the two numbers."

(Comment: Since guessing is not an option, the mathematician is left with this simple admission.)

Euler: "That was clear to me."

(Comment: This unequivocal answer suddenly puzzles Gauss. Why does Euler know so well that he (Gauss) cannot determine the numbers? At this moment Gauss has to assume that 28 cannot be the sum that Euler received, there otherwise he would have to express himself differently, for example: “Oh, could have been” [namely the numbers 5 and 23 or 11 and 17], but since he says that it is clear to him, he lets us see that his sum is equal can only be broken down into factors, which leads to products that have several possible pairs of factors. But this is only the case with the sum 17. That means: It must be the numbers 4 and 13.)

Gauss: "Now I know the two numbers."

(Comment: This answer again makes Euler ponder. How can Gauss know the numbers based on his utterance? Gauss must have been very close to the solution. He looks again at Table 1. Here, of course, the line that strikes you immediately is that only If this were the solution, Gauss would surely have broken down the product 52 into these factors and also broken down the possible summands into possible factors. In short: Gauss would have prepared Tables 1 and 2. For this case, he can Understand Euler Gauss's thoughts. Gauss can [as we know] only have two options. One that consistently contains several possible pairs of factors and one that also contains pairs of prime factors [and thus trivially solvable]. But Euler concludes with his statement: " It was clear to me that “this sum [28] with the trivial solutions [from a linguistic point of view] remains. So only the other [17] remains: It must be the numbers 4 and 13 .)

Euler: "Then I know her now too."

Web links

• Number puzzle Here there is a more difficult version of this puzzle by Robert Sontheimer
• Easily comprehensible programming solution

References

1. ^ Hans Freudenthal , Nieuw Archief Voor Wiskunde, Series 3, Volume 17, 1969, page 152
2. ↑ The Impossible Puzzle ( Memento of the original from December 20, 2014 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. with variants of the puzzle and a link to solutions.