EXPLAIN EXTENDED

Here is a riddle I read a long time ago in Nauka i Zhizn, a popular Russian science magazine.

The Sultan's Riddle

Once upon a time there was a Sultan who was looking for a vizier to help him rule his country. It became known to him that among the multitudes of his loyal subjects that populated his glorious empire, two were regarded as the most wise and sharp in mind. Their names were Ali-ibn-Wali and Wali-ibn-Ali. The Sultan summoned the men to his palace and ordered them to stand in front of him.

"It has come to my attention that you, Ali, and you, Wali, are the smartest men of all the people of Faith. Is that right?", asked the Sultan, sipping his sharbat. "We do know a thing or two of the beasts of the land and the fish of the sea and stars of the sky, indeed, but your sheer wisdom, o Great Sultan, outshines whatever puny bits of knowledge we might have and makes words coming from our mouths sound like child's babbling", said the wise men, kneeling before the Sultan (as they were truly wise and knew how to talk to a man of high power).

"Good, good," said the Sultan with a sneer, "I see you are good with words but are you as good with numbers? Let me test your knowledge."

"A diviner once came to my palace and revealed two numbers to me," continued the Sultan, "one being my lucky number, and another one being my unlucky number. Each of these numbers is more than one and less than a hundred. I never tell these numbers to anyone as this could put the fate of my empire in enemy's hands. But I am going to multiply those numbers and secretly tell their product to you, Ali, and then I am going to add those numbers and secretly tell their sum to you, Wali. If you are as wise as they say, you will have no problem figuring out those numbers."

And then he ordered the men to approach him and kneel before him, and he whispered the numbers to their ears.

Once Ali raised from his knees, he stood there for a moment, silently moving his lips, and then said: "Unfortunately, о the Brightest One, I cannot tell you those numbers."

"This is true," confirmed Wali, stroking his beard.

"Thank you, most esteemed Wali," said Ali, his face brightening with joy. "Now I can tell those numbers."

"Thank you too, most esteemed Ali," answered Wali. "Now I can tell them too."

And they whispered the numbers to the ear of the astonished Sultan, and they turned out right. And they both were appointed viziers.

Can you tell those numbers?

At first glance, this riddle seems impossible to solve. However, if we carefully read and parse what did Ali and Wali say, we can easily solve this riddle too. And to make things even more fun, we'll do that in SQL.

Ali's first phrase

What did Ali mean when he said he could not tell the numbers? He's a good mathematician so if he says "I can't," he means there is not enough data for him. All he knows about those numbers is their product and the fact the numbers are from 2 to 99 inclusive.

Let's assume, for the sake of argument, that the Sultan had numbers 3 and 7 in mind. Their product would be 21. Would a good mathematician, or, for that matter, any middle school student be having problems telling what two numbers from 2 to 99 could give 21 as their product? Of course not!

But what if the numbers were 4 and 6? Their product would be 24. But 8 times 3 would also give 24, and so would 2 times 12. All those numbers could be possible answers to the Sultan's riddle, as far as Ali knew, so he would not be able to tell the original numbers without some other information.

Let's try to figure out what the Sultan could tell Ali.

There is a very important fact about numbers in math, so important that it sometimes is called the fundamental theorem of arithmetic. It says that any number is either prime itself (cannot be divided without a remainder by any other number higher than 1), or is a product of prime numbers, and the set of those numbers is unique, up to the order. It means that 24 is a product of 2, 2, 2 and 3, all of which are prime, and we cannot come up with a set of prime numbers other than three 2's and one 3 so that their product would be 24. The process of defining the set of prime numbers a number is made of is called prime factorization.

While prime factorization is unique, some numbers can still be products of two different sets of numbers (which cannot be prime anymore of course). It means that if we combine the prime factors differently, we can come up with two or more different pairs of non-prime factors. For instance, 24 = (2×2×2)×3 = 8×3, or 24 = (2×2)×(2×3) = 4×6, or 24 = 2×(2×2×3) = 2×12. Because of the fundamental theorem we cannot take any primes other than those that were there in the number in the first place, but we can very well combine the existing ones in different ways to get new pairs of factors.

It's easy to see that there should be more than two prime factors in the first place for this to work. If we only have 3 and 7, we don't have much room for combination, so there is only way to pair factorize 21 (namely, 21 = 3×7).

What about 27? It's 3×3×3, so it looks good at first glance, but we are talking pairs of factors here. If we try to factor it into a pair of numbers, we will always be getting 3 and 9, which would be good enough for Ali.

What about 388? It's prime factorized as 97×2×2 so it looks like a good candidate too. However, it can be pair factorized as either 2×(2×97) = 2×194 or (2×2)×97 = 4×97, and 194 is larger than 99, so could not possibly be one of the Sultan's numbers either. Ali would notice it of course and could be able to tell the
only pair which satisfied all the conditions

So what did Ali say in fact? He said: "my number can be factorized into more than one pair of integer factors from 2 to 99". And this defines a set of numbers which we can try and build in SQL.

For starters, we need a way to take a number and prime factorize it. This task is considered notoriously hard to perform on a computer if the number is large and in fact, this hardness is what a great deal of the modern computer security is based upon. However, we only deal with relatively small numbers here, up to 9801 (that's the largest number the Sultan could tell Ali), so we can do it with a quite inefficient but very simple recursive algorithm. We will take the number, find its largest factor (not necessarily prime) by exhaustive search from its square root down to 2, find another factor (simply be dividing by the first one), then repeat the algorithm recursively for each of the divisors we just found. If we fail to find a divisor on any step, we know the original number was prime.

Here's how we do that in PostgreSQL:

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        )
SELECT  *
FROM    all_factors
WHERE   initial = 96
        AND final

It is what the factoring query looks it its most raw form (we are trying it on the number 96). It turns out this number can be prime factorized into five 2's and one 3.

The next step would be generating all possible factor pairs from the sets of prime factors. To do that, we would also need to resort to a little bit of set theory. We already know that the number 96 above can be factorized into six prime numbers, five of them 2 and another one 3. To build all possible lists of pairs from them, we need to come up with a list of all possible combinations of these numbers (just first, then first and second, then first and third, etc.), each of these combinations making up the first number in the pair. The second number in the pair would, of course, be just the quotient from the division of the original number by the first number in the pair.

So we have a set of prime factors and need to come up with a way to build all possible subsets of it. The set of all subsets is called a power set in math and there is a recursive algorithm to build it. Strictly speaking, the empty set (no elements at all) and the full set (all the factors) are in the power set too, but we are not interested in them, as they would not make a good item for our pair of factors. Also, each pair would be counted twice. If we take some subset of prime numbers for the first number in the pair, the rest of the set (or, as a mathematician would say, the subset's complement) will make the second pair. And when it is the complement's turn to make the first number, it would yield the same pair, just with the order reversed. Usually, we would want to optimize the recursion a little to avoid second evaluation of the sets, but let's just keep the query simple and use good old DISTINCT to handle the duplicates for us.

To build the power set, we should give each unique prime factor a number (so we could tell them apart) and record this number in the anchor part of the recursion query. In the recursive part, we'll be picking only the factors with numbers up to the anchor number, non-inclusive. On the first step this means: for the anchor 6, apply recursion to records [1..5], for the anchor 5, apply recursion to record [1..4], etc. On the second step this would mean: for the anchor [5, 6] apply recursion to [1..4], for the anchor [4, 6] apply recursion to [1..3], etc.; and so on. It is easy to see that this way the recursion would be applied to each of the possible subsets, to each exactly once.

Finally, we need to take every factor from the power set and find its complement, then build a unique pair from them (put the smaller one first and the larger one second).

Here's what the query looks like (I'm only factorizing the numbers from 1 to 24 here for the sake of brevity):

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  initial,
                (LEAST(one, two), GREATEST(one, two)) pair
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
        )
SELECT  DISTINCT
        initial, pair
FROM    pairs
WHERE   initial <= 24
ORDER BY
        initial, pair

We can see that some of the possible numbers from 4 to 9801 are not even there (because they are prime and could not give us a pair of factors); others are listed more than once (like 12, 16, 18, 20 and 24). Those listed more than once are exactly the numbers the Sultan could give to Ali: the reason Ali could not tell the pair is that there is more than one.

Let's try and present them on a grid:

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  initial,
                (LEAST(one, two), GREATEST(one, two)) pair
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
        ),
        alis_first AS
        (
        SELECT  *
        FROM    (
                SELECT  initial, COUNT(DISTINCT pair) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        )
SELECT  '   ' || STRING_AGG(CASE WHEN x % 10 = 0 THEN (x / 10)::TEXT ELSE ' ' END, '')
FROM    generate_series(0, 99) x
UNION ALL
SELECT  '   ' || STRING_AGG((x % 10)::TEXT, '')
FROM    generate_series(0, 99) x
UNION ALL
(
SELECT  LPAD(y::TEXT, 2, '0') || ' ' || STRING_AGG(CASE WHEN alis_first_ways IS NOT NULL THEN '.' ELSE ' ' END, '' ORDER BY x)
FROM    generate_series(0, 99) y
CROSS JOIN
        generate_series(0, 99) x
LEFT JOIN
        alis_first
ON      initial = (y * 100) + x
GROUP BY
        y
ORDER BY
        y
)

Ali's numbers are presented in a centesimal (100-based) system on a grid. To see which number does a cell correspond to, take the cell's row number, multiply it by 100 and add the cell's column number.

Wali's response

Now we have a list of numbers which the Sultan could tell Ali. It is quite an extensive list; there are 1068 entries in it (I counted), and Ali could have any of those numbers. However, the list of the numbers which would allow Ali to make an instant guess is even larger; namely, there are 1775 such numbers (I counted too).

Wali could not know which number did the Sultan give to Ali and, as a mathematician, he is not likely to give statements not backed up by sound logic, no matter how close he is to Ali or to what extent does he trust in his mathematical abilities. So what did Wali mean exactly when he backed up Ali by confirming Ali could not name the original numbers?

Remember that Wali does not know the numbers or their product. What he knows, however, is their sum, which could be any number from 4 (2 + 2) to 198 (99 + 99). Depending on what the sum is, it could be possible to tell the terms just from knowing the sum. For instance, if the number the Sultan gave to Wali were 4, it would be enough for him to tell the original numbers, as the only two numbers from 2 to 99 that would give 4 as a sum, are 2 and 2. Same reason stands for the numbers 5, 198 and 197. The other numbers, unfortunately, are not that easy: 6 is 2 + 4 or 3 + 3, other numbers offer even more possibilities.

Imagine Wali was given the number 5 in the first place. It means that the only possible original numbers are 2 and 3. It would unequivocally say Ali was given the number 6 and there's no chance Ali could not figure the only factors of such a simple number. So if Wali's number were 5, he would have never backed up Ali.

Let's consider a more complicated example. Say the Sultan told Wali the number 9. It can be represented as 2 + 7, 3 + 6 or 4 + 5, which Wali is, of course, aware of. And now that he knows the possible terms in his sum, he could also tell the possible products (i. e. Ali's numbers). Those would be 2×7 = 14, 3×6 = 18 and 4×5 = 20. Being a renowned mathematician, Wali knows that 20 and 18 could not be factorized into a unique pair of numbers (remember that 20 = 4×5 = 2×10 and 18 = 3×6 = 2×9). 14, however, could be factorized to 2 and 7 only, and as far as Wali is concerned, there is a chance the Sultan would tell Ali the number 14 and not any other number.

It would mean there was a possibility Ali could tell the numbers right away, and for a mathematician, even a single counterexample would be enough to say some statement was not true.

Wali would never say something was true unless he knew that for a fact. But how could he be sure?

Let's look into one more number, 11. It's 2 + 9 = 3 + 8 = 4 + 7 = 5 + 6. For Ali, that would mean 18, 24, 28 or 30. If we look closely at the grid above and try to find those numbers, we will see that there are dots on each of the cells corresponding to these numbers.

Now this means that no matter what the original numbers were, Ali would not be able to tell them just from knowing their product. And this is, finally, enough for Wali to back up his colleague's claim.

So what Wali in fact said was "My number is such that no two terms from 2 to 99 are unique factors of their product in that range". As we have seen, 11 is an example of such a number; 9 and 5 are not.

How can we build a set of numbers like that?

Let up make another grid, this time changing the way we represent Ali's numbers. Instead of having hundreds and units for the axes and adding them up, we will use numbers from 2 to 99 and multiply them. The grid's layout would change drastically, as this way we will have more than one cell corresponding to each of the numbers. First, any number there can be represented both as x×y and y×x; second, by definition, each number in Ali's list can be factorized in more than one way, so there will be at least 4 points for each Ali's number on the new grid.

Here's how it looks:

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  initial,
                (LEAST(one, two), GREATEST(one, two)) pair
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
        ),
        alis_first AS
        (
        SELECT  *
        FROM    (
                SELECT  initial, COUNT(DISTINCT pair) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        )
SELECT  '    ' || STRING_AGG(CASE WHEN x % 10 = 0 THEN (x / 10)::TEXT ELSE ' ' END, '')
FROM    generate_series(2, 99) x
UNION ALL
SELECT  '    ' || STRING_AGG((x % 10)::TEXT, '')
FROM    generate_series(2, 99) x
UNION ALL
(
SELECT  LPAD(y::TEXT, 3, '0') || ' ' || LEFT(STRING_AGG(CASE WHEN alis_first_ways IS NOT NULL THEN '.' ELSE ' ' END, '' ORDER BY x), 99)
FROM    generate_series(2, 99) y
CROSS JOIN
        generate_series(2, 99) x
LEFT JOIN
        alis_first
ON      initial = x * y
GROUP BY
        y
ORDER BY
        y
)

Those are Ali's numbers represented by the dots on the grid, but what about Wali? He knows the sum of the numbers and the fact that the product of any of its possible terms would not factorize uniquely. All the terms of a single number would reside on a diagonal going from top right to bottom left, so what Wali would do is have a look at the diagonal corresponding to his number and tell if it has some cells.

If there is but a single empty cell there, it leaves a possibility for Ali to tell the numbers right away; if there's none, there's no chance for Ali to guess the numbers from their product. Let's highlight Wali's numbers 9 and 11 (or 9 and B in hexadecimal notation):

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  initial,
                (LEAST(one, two), GREATEST(one, two)) pair
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
        ),
        alis_first AS
        (
        SELECT  *
        FROM    (
                SELECT  initial, COUNT(DISTINCT pair) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        )
SELECT  '    ' || STRING_AGG(CASE WHEN x % 10 = 0 THEN (x / 10)::TEXT ELSE ' ' END, '')
FROM    generate_series(2, 99) x
UNION ALL
SELECT  '    ' || STRING_AGG((x % 10)::TEXT, '')
FROM    generate_series(2, 99) x
UNION ALL
(
SELECT  LPAD(y::TEXT, 3, '0') || ' ' || LEFT(STRING_AGG(CASE WHEN alis_first_ways IS NOT NULL THEN CASE WHEN x + y IN (9, 11) THEN TO_HEX(x + y) ELSE '.' END ELSE ' ' END, '' ORDER BY x), 99)
FROM    generate_series(2, 99) y
CROSS JOIN
        generate_series(2, 99) x
LEFT JOIN
        alis_first
ON      initial = x * y
GROUP BY
        y
ORDER BY
        y
)

We see there are two gaps on the diagonal 9, one at 2×7 and another one at 7×2 (which is no surprise, because as we said, the grid is symmetrical). However, there are no gaps on the diagonal 11. This means 9 cannot be Wali's number and 11 can, which is what we have figured out earlier;

Let's try to build the list of all possible Wali's numbers in SQL. To do this, we will examine each possible sum (that is all numbers from 4 to 198) and make sure all the products of its possible terms are in Ali's first list:

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  initial,
                (LEAST(one, two), GREATEST(one, two)) pair
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
        ),
        alis_first AS
        (
        SELECT  *
        FROM    (
                SELECT  initial, COUNT(DISTINCT pair) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        ),
        walis_list AS
        (
        SELECT  x
        FROM    generate_series(4, 198) x
        CROSS JOIN
                LATERAL
                generate_series(2, x - 2) y
        LEFT JOIN
                alis_first
        ON      initial = y * (x - y)
        GROUP BY
                x
        HAVING  COUNT(*) = COUNT(initial)
        )
SELECT  *
FROM    walis_list
ORDER BY
        x

It turns out there are only ten numbers the Sultan could tell Wali so that he would be able to back up his colleague's claim with confidence.

Ali's second phrase

We know the possible set of numbers Wali could be told, and of course so does Ali (he did the same calculations as we did, all in his head, standing in front of a mighty monarch!). It gives him a bit of information he lacked initially: now he does not only know the product of the Sultan's numbers but also what their sum can be. It has to be one of the ten numbers on Wali's list; otherwise, Wali would not have made his claim. All Ali has to do now is to go through the list of possible factor pairs and choose those that would add up to one of Wali's numbers. If you know both the sum and the product of two numbers, you can easily tell them by solving a simple quadratic equation: x² - Sx + P = 0, where S is the sum and P is the product. The two solutions of the equation would correspond to the two numbers.

It's not however always possible for Ali to do that. If, for instance, he was given the number 30 by the Sultan, two possible factorizations for it would be 5×6 and 2×15. 5 + 6 = 11 (which is a Wali's number) and 2 + 15 = 17 (which is a Wali's number as well). Ali would not be so glad and would never tell he knew the number, be it the case. It means Ali's number has three important properties: first, it's in the initial Ali's list; second, it has factors which add up to a Wali's number; third, there is only one set of factors like this. What Ali said is "My number is Ali's number, and it has exactly one set of numbers which add up to a Wali's number" (I've replaced the longer definitions from above with "Ali's number" and "Wali's number").

Let's see what could Ali possibly mean. We will return Ali's second numbers, their factors and the factors' sums (which should be Wali's numbers):

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  DISTINCT
                initial, one, two
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
                AND one < two
        ),
        alis_first AS
        (
        SELECT  initial
        FROM    (
                SELECT  initial, COUNT(DISTINCT (one, two)) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        ),
        walis_list AS
        (
        SELECT  x
        FROM    generate_series(4, 198) x
        CROSS JOIN
                LATERAL
                generate_series(2, x - 2) y
        LEFT JOIN
                alis_first
        ON      initial = y * (x - y)
        GROUP BY
                x
        HAVING  COUNT(*) = COUNT(initial)
        ),
        alis_second AS
        (
        SELECT  initial AS ali, one, two, one + two AS wali
        FROM    (
                SELECT  initial, one, two,
                        COUNT(*) OVER (PARTITION BY initial) cnt
                FROM    pairs
                WHERE   initial IN
                        (
                        SELECT  initial
                        FROM    alis_first
                        )
                        AND (one + two) IN
                        (
                        SELECT  x
                        FROM    walis_list
                        )
                ) q
        WHERE   cnt = 1
        )
SELECT  *
FROM    alis_second
ORDER BY
        wali

There are as many as 86 different numbers Ali have been given, but that's of no concern to him of course. He knows the product of the two numbers, and through careful and thorough logical reasoning he was also able to figure out their sum. Hence, he could tell them. Unfortunately, we still cannot: we don't have enough information yet. Let's see what does Wali have to say, though.

Wali's second response

Somehow, when Wali learned that Ali was able to tell the numbers, he was sure he could indeed.

Wali knows for sure what the sum of the numbers is, and also knows what could their product be (it has to be one of the 86 numbers from Ali's second list), and its factors should add up to his sum. That's still not enough for him to tell the original numbers, though.

For instance, if Wali's number was 11, Ali's one could be 18=2×9, 24 = 3×8 or 28 = 4×6 (but not 30 = 5×6, as we learned earlier: it's on the Ali's first list but not the second). This way, Wali would have never made his second remark if his number was 11: for all he knew, it could be any pair of numbers from the list above. And yet he did claim he was able to tell the numbers.

It could only mean one thing: there was only one Ali's second number whose factors added up to the number Wali knew.

Let's build a list of numbers sharing this property:

WITH    RECURSIVE
        all_factors (initial, factor, final) AS
        (
        SELECT  s, s, FALSE
        FROM    generate_series(2, 99 * 99) s
        UNION ALL
        SELECT  initial, f, d IN (1, factor)
        FROM    (
                SELECT  initial, factor, d
                FROM    all_factors
                CROSS JOIN
                        LATERAL
                        (
                        SELECT  d
                        FROM    generate_series(TRUNC(SQRT(factor))::INTEGER, 1, -1) d
                        WHERE   factor % d = 0
                        LIMIT 1
                        ) q (d)
                WHERE   NOT final
                ) q
        CROSS JOIN
                LATERAL
                (
                VALUES
                (d),
                (factor / d)
                ) p (f)
        WHERE   f NOT IN (initial, 1)
        ),
        factors AS
        (
        SELECT  initial, factor,
                ROW_NUMBER() OVER (PARTITION BY initial ORDER BY factor) rn
        FROM    all_factors
        WHERE   final
        ),
        powerset_factors AS
        (
        SELECT  initial, factor, rn
        FROM    factors
        UNION ALL
        SELECT  p.initial, p.factor * f.factor, f.rn
        FROM    powerset_factors p
        JOIN    factors f
        ON      f.initial = p.initial
                AND f.rn > p.rn
        ),
        pairs AS
        (
        SELECT  DISTINCT
                initial, one, two
        FROM    (
                SELECT  initial,
                        factor one,
                        initial / factor two
                FROM    powerset_factors
                WHERE   initial NOT IN (1, factor)
                ) q
        WHERE   one BETWEEN 2 AND 99
                AND two BETWEEN 2 AND 99
                AND one < two
        ),
        alis_first AS
        (
        SELECT  initial
        FROM    (
                SELECT  initial, COUNT(DISTINCT (one, two)) alis_first_ways
                FROM    pairs
                GROUP BY
                        initial
                ) q
        WHERE   alis_first_ways >= 2
        ),
        walis_list AS
        (
        SELECT  x
        FROM    generate_series(4, 198) x
        CROSS JOIN
                LATERAL
                generate_series(2, x - 2) y
        LEFT JOIN
                alis_first
        ON      initial = y * (x - y)
        GROUP BY
                x
        HAVING  COUNT(*) = COUNT(initial)
        ),
        alis_second AS
        (
        SELECT  initial AS ali, one, two, one + two AS wali
        FROM    (
                SELECT  initial, one, two,
                        COUNT(*) OVER (PARTITION BY initial) cnt
                FROM    pairs
                WHERE   initial IN
                        (
                        SELECT  initial
                        FROM    alis_first
                        )
                        AND (one + two) IN
                        (
                        SELECT  x
                        FROM    walis_list
                        )
                ) q
        WHERE   cnt = 1
        ),
        walis_second AS
        (
        SELECT  ali, one, two, wali
        FROM    (
                SELECT  *,
                        COUNT(*) OVER (PARTITION BY wali) cnt
                FROM    alis_second
                ) q
        WHERE   cnt = 1
        )
SELECT  *
FROM    walis_second
ORDER BY
        wali

Here we are!

The Sultan's lucky and unlucky number were 4 and 13 (try to guess which was which). Their product was 52, and their sum was 17.

Ali could not tell those numbers right away (they could as well be 2 and 26).

Wali knew that: all numbers adding up to 17 cannot be uniquely factorized. Other numbers like that are 11, 23, 27, 29, 35, 37, 41, 47 and 53

Having learned that the sum of his factors should be one of Wali's numbers, Ali could tell those numbers: if those were 2 and 26, they would add up to 28, as would 23 and 5 which are both prime. 28 is not a Wali's number, meaning Wali could not possibly have made his remark if his number was 28.

Having heard that Ali could ultimately tell his numbers, Wali could tell them too: any terms other than 4 and 13 would produce a number which could be factorized in at least two Wali-compatible ways. If those were 2 and 15, Ali's number would have been 2×15 = 30 = 5×6, giving 5 + 6 = 11. There is no way for Ali to know if Wali's number were 17 or 11, just the fact that it could be either of them and hence he would not be able to tell his numbers in the first place. Same logic holds for 3 and 14 (3 + 4 = 17, 2 + 21 = 23, 3×14 = 2×21); 5 and 12 (5 + 12 = 17, 20 + 3 = 23, 5×12 = 20×3), etc. 4 and 13 were the only suitable pair.

What we did to solve that riddle is just carefully translate it from a human language to SQL and run the SQL, which gave us back the only possible answer.

You can view the queries here: https://github.com/quassnoi/explain-extended-2017

I sincerely wish all the riddles and challenges the New Year has for you could be solved just as easily!

Previous New Year posts:

• Happy New 2010 Year!
• Happy New 2011 Year!
• Happy New 2012 Year!
• Happy New 2013 Year!
• Happy New 2014 Year!
• Happy New 2015 Year!
• Happy New 2016 Year!