Post date: Sep 29, 2014 11:55:37 PM
"Find the smallest odd composite number that is not equal to the sum of a prime and two times a perfect square."
This one is annoying because it's a fishing expedition. We need to find the first value that doesn't match these criteria, but there are no clues given (other than knowing the answer) about what order of magnitude it is. Lucky for us, it's small. So it didn't take a lot of retries.
CREATE TABLE #Integers (i int not null primary key)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i)
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
)
INSERT INTO #Integers (i)
SELECT i
FROM Integers
WHERE i >= 10
-- Eratosthenes sieve
CREATE TABLE #Primes (i int not null primary key)
INSERT INTO #Primes
SELECT i
FROM #Integers
WHERE i >= 2
DECLARE @num int = 1
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(9999)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
-- Fill a table with sums of primes and 2 * squares.
CREATE TABLE #Goldbach (i bigint not null)
INSERT INTO #Goldbach
SELECT p.i + 2 * SQUARE(i.i)
FROM #Primes p
CROSS JOIN #Integers i
-- Fish on!
SELECT MIN(i)
FROM #Integers
WHERE i % 2 > 0 -- odd
AND i NOT IN (SELECT i FROM #Primes) -- composite (not prime)
AND i NOT IN (SELECT i FROM #Goldbach) -- not a sum of a prime and twice a square
AND i > 1 -- 1 isn't composite either
DROP TABLE #Goldbach
DROP TABLE #Primes
DROP TABLE #Integers