Post date: Jul 24, 2014 12:22:8 AM
"Find all equations of the form a * b = c where the digits in a, b, and c collectively use each of the integers between 1 and 9 exactly once. Sum the distinct values of c."
If we allow 4 digits or less between the two multipliers, then the max result, even if we allowed all 9s, is 9801, itself 4 digits, for a total of 8 digits. So we know the two multipliers must be 5 or more digits together. The minimum we can get from 6 digits of multipliers, even if we allowed all 1, is 11111, for a total of 11 digits. So we know that there are exactly 5 digits of multipliers a and b, and all products c are exactly 4 digits each. This limits our options to a reasonable amount.
CREATE TABLE #Digits (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Digits VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
-- Fill a table of all possible products, each a 4 digit integer that has no duplicate digits.
CREATE TABLE #Products (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Products
SELECT 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Digits o
INNER JOIN #Digits t
ON t.i <> o.i
AND t.i > 0
INNER JOIN #Digits h
ON h.i <> o.i
AND h.i <> t.i
AND h.i > 0
INNER JOIN #Digits k
ON k.i <> o.i
AND k.i <> t.i
AND k.i <> h.i
AND k.i > 0
WHERE o.i > 0
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Integers
SELECT 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Digits o
CROSS JOIN #Digits t
CROSS JOIN #Digits h
CROSS JOIN #Digits k
CROSS JOIN #Digits k10
WHERE 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i > 0
CREATE TABLE #Factors (
product INT NOT NULL,
f1 VARCHAR(4) NOT NULL,
f2 VARCHAR(4) NOT NULL,
combo VARCHAR(12) NOT NULL,
PRIMARY KEY (product, f1, f2)
)
-- Take the products and find their factors.
-- The combo field contains all three numbers concatenated.
INSERT INTO #Factors (product, f1, f2, combo)
SELECT p.i, f.i, p.i/f.i, CONVERT(varchar(4),p.i) + CONVERT(varchar(4),f.i) + CONVERT(varchar(4),p.i/f.i)
FROM #Products p
INNER JOIN #Integers f
ON p.i % f.i = 0
AND f.i <= SQRT(p.i)
-- Valid products are ones where exactly 9 distinct digits are used between all 3 numbers, not including 0.
; WITH Products AS
(
SELECT product, f1, f2
FROM #Factors f
INNER JOIN #Digits d
ON f.combo LIKE '%' + CONVERT(char(1),d.i) + '%'
AND d.i > 0
WHERE LEN(combo) = 9
GROUP BY product, f1, f2
HAVING COUNT(DISTINCT d.i) = 9
)
SELECT SUM(DISTINCT product)
FROM Products
DROP TABLE #Factors
DROP TABLE #Products
DROP TABLE #Integers
DROP TABLE #Digits