Freudenthal Impossible Puzzle Solution in SQL

[mikemciver]

Puzzle explained in detail here

Saw it on another Quant site but they want a DNA sample to join their forum.

I'm not really sure I fully understand the all theory behind the math but I was able to port it over to SQL . . . the puzzle has been around for a while.

• Two people, S and P and two numbers x and y . . .
  • S is told the sum of the numbers
  • P is told the product.
  • Both are told 1 < x < y < 100, x + y <= 100
• This is all the info they exchange between themselves
  • P- "I don't know the two numbers"
  • S- "I knew you didn't"
  • P- "Now I know"
  • S- "Now I do too"

Objective is to determine x and y.

Here's the SQL . . . there's supposedly only one right answer but I saw some debate on this so the query returns 10 records ranked. I've run it up to 800 vice 100 with the same results.

(Done on MSSQL 08)
SET NOCOUNT ON

/*** BEGIN: SETUP NUMBER RANGE ACCORDING TO PROBLEM CONSTRAINTS AND FLAG PRIMES ***/
DECLARE @iSTART INT = 2,
@iEND INT = 100 --800

DECLARE @t TABLE
(
[VAL] INT,
[ISPRIME] INT,
[PRIME+2] AS ([VAL] + 2) * [ISPRIME]
)

DECLARE @i INT = @iSTART

WHILE @i BETWEEN @iSTART AND @iEND
BEGIN

INSERT @t([VAL],[ISPRIME])
SELECT A.[VAL],
CASE
WHEN B.[VAL] > 1
THEN 0
ELSE 1
END
FROM (SELECT @i AS [VAL]) A LEFT JOIN
(
SELECT DISTINCT
A.[VAL]
FROM (SELECT @i AS [VAL]) A CROSS JOIN
@t B
WHERE A.[VAL] <> B.[VAL]
AND B.[VAL] < @iEND / 2
AND A.[VAL] % B.[VAL] = 0
) B
ON A.[VAL] = B.[VAL]

SET @i += 1
END;

--SELECT *
--FROM @t
--RETURN;
/*** END: SETUP NUMBER RANGE ACCORDING TO PROBLEM CONSTRAINTS AND FLAG PRIMES ***/


/*** BEGIN: THE RESULT QUERY ***/
WITH [CTE]
(
[A_VAL],
[B_VAL],
[SUM],
[PRODUCT],
[CNT_SUM],
[CNT_PRODUCT]
)
AS
(
SELECT A.[VAL] AS [A_VAL],
B.[VAL] AS [B_VAL],
A.[VAL] + B.[VAL] AS [SUM],
A.[VAL] * B.[VAL] AS [PRODUCT],
COUNT(A.[VAL] + B.[VAL]) OVER(PARTITION BY A.[VAL] + B.[VAL]) AS [CNT_SUM],
COUNT(A.[VAL] * B.[VAL]) OVER(PARTITION BY A.[VAL] * B.[VAL]) AS [CNT_PRODUCT]
FROM @t A INNER JOIN
@t B
ON A.[VAL] < B.[VAL]
WHERE A.[VAL] + B.[VAL] < 100
)
SELECT TOP 10
A.[A_VAL],
A.[B_VAL],
A.[SUM],
A.[PRODUCT],
A.[CNT_SUBSET_SUM] AS [RANK]
FROM (
SELECT A.*,
COUNT(A.[SUM]) OVER(PARTITION BY A.[SUM]) AS [CNT_SUBSET_SUM]
FROM (
SELECT
A.*,
COUNT(A.[PRODUCT]) OVER(PARTITION BY A.[PRODUCT]) AS [CNT_SUBSET_PRODUCT]
FROM CTE A INNER JOIN
(
SELECT DISTINCT
A.[SUM]
FROM CTE A LEFT JOIN
(
SELECT DISTINCT
[SUM]
FROM CTE
WHERE [CNT_SUM] = 1
OR [CNT_PRODUCT] = 1
) B
ON A.[SUM] = B.[SUM] LEFT JOIN
@t C
ON A.[SUM] = C.[PRIME+2]
WHERE B.[SUM] IS NULL
AND A.[SUM] % 2 > 0
AND C.[PRIME+2] IS NULL
) B
ON A.[SUM] = B.[SUM]
) A
WHERE A.[CNT_SUBSET_PRODUCT] = 1
) A
ORDER BY
A.[CNT_SUBSET_SUM],
A.[A_VAL],
A.[B_VAL],
A.[SUM],
A.[PRODUCT]
/*** END: THE RESULT QUERY ***/

 

[pruse]

The problem doesn't require any sophisticated mathematics.

The first statement merely implies that xy has at least 6 factors (since it can be factored in at least two ways as a product of distinct numbers greater than 1), while the second statement implies that for any pair (a, b) of numbers adding up to x+y the product ab has at least 6 factors, etc... Then checking a couple of cases does the job

 

[Dragunov]

This is interesting. Why did you have to use SQL though... oh I see.

 

[mikemciver]

Someone asked if it could be done in SQL.