Sauron says to Dumbledore and Merlin…

Written by Written by Sergei

This sounds like a lame cross-genre joke, but it is not. It is a lame cross-genre math problem. I have to admit, it didn’t have those names when I read about it, but I wanted to make it a bit more epic. So,

Sauron says to Dumbledore and Merlin, finally I have captured you both. Now I shall select two numbers, greater than one, less than a hundred. Dumbledore shall know their product and Merlin shall know their sum. If you, fools, will be able to tell me the numbers I have chosen, I shall let you free. Otherwise I shall kill you both.

And so he does, whispers something into Dumbledore’s ear, then into Merlin’s.

Dumbledore looks at Merlin, sighs and admits, “I cannot name these numbers”. Merlin shrugs, “I knew it”. “Oh” — Dumbledore blinks — “but then I can name them”. “So do I”, quickly adds Merlin.

And, of course, they do. End of story.

It’s often said that if all you have is a hammer, everything starts looking like a nail. And all I have at the moment is an SQL database. Let’s use it to untangle this story.

It is, likely, possible to solve this problem with one gigantic SQL query1, but it’s far easier to proceed step by step and for that we’ll need a table:

CREATE TABLE t AS SELECT s1.seq a, s2.seq b
    FROM seq_2_to_99 s1, seq_2_to_99 s2
        WHERE s1.seq < s2.seq;

And here it is. A beautiful table filled with all possible combinations of numbers Sauron could have chosen. If you prefer to stay within the realms of the SQL Standard or simply use another database, you’ll need to use the WITH clause to fill the table, but I’m not bound by the real-world limitations here.

There are many combinations of numbers and many different values for a sum and a product. Some are common, others are rare. Certain products happen only ever once:

SELECT a,b,a+b,a*b FROM t GROUP BY a*b HAVING COUNT(*)=1;
+----+----+-----+------+
| a  | b  | a+b | a*b  |
+----+----+-----+------+
|  2 |  3 |   5 |    6 |
|  2 |  4 |   6 |    8 |
...
| 97 | 99 | 196 | 9603 |
| 98 | 99 | 197 | 9702 |
+----+----+-----+------+

But these are not the numbers we seek. If Dumbledore would have heard “8”, he would have known both numbers instantly. Or if he would have heard “9603”. Or, say, “187” (a product of two prime numbers). The number he has heard must have definitely been not on this list.

But wait, Merlin knew it. Whatever number Merlin has heard, there were many ways to split it into two addends. And by multiplying them one would get many different products. Merlin knew that Dumbledore was unable to figure out the numbers, because none of the products one could possibly get from the addends of Merlin’s sum were on the list above. Otherwise Merlin couldn’t have been so sure. In other words, the number that Merlin has heard was not in the third column of the table above.

Time to prune the table. Let’s remove all those numbers that we know Sauron could not have chosen, numbers with the sum that Merlin could not have heard:

DELETE FROM t WHERE a+b IN
    (SELECT a+b FROM t GROUP BY a*b HAVING COUNT(*)=1);

Back to Dumbledore. As soon as he has heard Merlin’s wise words, he knew he was saved. Being a wizard he, of course, performed all the above deductions in his head and much faster than it took you to read this post. The table still has 145 rows and we do not know what numbers Sauron had. But Dumbledore knew their product — and it helped him to find that one row that was a key to his life and freedom.

Happy for Dumbledore we know that whatever product he had, it must have been present in the table only once. Let’s remove all other rows now:

DELETE FROM t WHERE a*b IN
    (SELECT a*b FROM t GROUP BY a*b HAVING COUNT(*)>1);

And Merlin — Dumbledore’s words was all he needed. He knew not the product of the numbers, only the sum. But he now knew that this product was present only once in the now-only-86-rows table. Knowing that and the sum was enough for him to get out. Apparently, his sum too was present only once there. What a stroke of luck!

This last bit of information was all we needed as well:

SELECT a,b,a+b,a*b FROM t GROUP BY a+b HAVING COUNT(*)=1;
+---+----+-----+-----+
| a | b  | a+b | a*b |
+---+----+-----+-----+
| 4 | 13 |  17 |  52 |
+---+----+-----+-----+

1) It turned out that SQL standard all-in-one-query solution is rather easy to assemble from the above. Without further explanations, here it is:

WITH RECURSIVE seq (i) AS
(
  SELECT 2 UNION ALL SELECT i+1 FROM seq WHERE i < 99
),
step1 (a,b) AS (
  SELECT s1.i, s2.i FROM seq s1, seq s2 WHERE s1.i < s2.i
),
step2 AS (
  SELECT * FROM step1 WHERE a+b NOT IN (SELECT SUM(a+b) FROM step1 GROUP BY a*b HAVING COUNT(*)=1)
),
step3 AS (
  SELECT * FROM step2 WHERE a*b NOT IN (SELECT a*b FROM step2 GROUP BY a*b HAVING COUNT(*)>1)
)
SELECT SUM(a),SUM(b),a+b,SUM(a*b) FROM step3 GROUP BY a+b HAVING COUNT(*)=1;

This worked in PostgreSQL, SQLite, SQL Server (after removing the keyword RECURSIVE), Oracle (after additionally adding FROM DUAL in SELECT 2), DB2 (same as Oracle, but a different 1-row table), and MySQL (without ONLY_FULL_GROUP_BY, I couldn’t make it work in default settings).