Post date: Aug 02, 2015 4:41:16 PM
"What is the lowest number that can be written as the sum of one or more primes in over 5,000 combinations of different sets?"
This one forces us to get the combinations, which made my original solution to the last problem take so long. Lovely. And we get no clues about the order of magnitude of the result, so I'll start with primes up to 1 million and hope it's good enough. If not, I'll have to try again with more.
CREATE TABLE #Primes (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Primes VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT 100000 * k100.i + 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Primes o
CROSS JOIN #Primes t
CROSS JOIN #Primes h
CROSS JOIN #Primes k
CROSS JOIN #Primes k10
CROSS JOIN #Primes k100
WHERE k100.i < 5
)
INSERT INTO #Primes
SELECT i
FROM Integers
WHERE i >= 10
DELETE FROM #Primes WHERE i IN (0, 1)
DECLARE @num int = 1
DECLARE @max int SELECT @max = MAX(i) FROM #Primes -- I always forget to change this limit when I copy/paste, so I'll look it up.
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(@max)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
DECLARE @t int = 4, @result int
WHILE 1 = 1
BEGIN
; WITH Combos (anchor, string, tail, total) AS
(
SELECT i, CONVERT(varchar(4000), RTRIM(i) + '.'), i, i
FROM #Primes
WHERE i <= @t
UNION ALL
SELECT c.anchor, CONVERT(varchar(4000),string + '.' + RTRIM(p.i)), p.i, total + p.i
FROM Combos c
INNER JOIN #Primes p
ON p.i <= c.tail
WHERE total + p.i <= @t
AND c.anchor <= @t
)
select @result = COUNT(DISTINCT string)
FROM Combos
WHERE total = @t
IF @result >= 5000 BREAK
SET @t = @t + 1
END
SELECT @t
DROP TABLE #Primes