Post date: Jun 18, 2014 1:20:20 AM
"Find all positive integers that are not the sums of two abundant numbers. Sum them."
Project Euler was hacked recently and is offline, so I'm having to depend on Google's cache for my math fix. I hope they are able to fix the site before the pages expire from the cache.
Anyway, this problem is a fairly simple query. We know that every number over 28123 is the sum of at least one set of two abundant numbers, and obviously if we add it to itself, we will be checking numbers up to 56246, which is more than we need but still a small set. We just need to get all the abundant numbers below 28123 (numbers larger than the sum of their factors), sum every combination, and find the numbers not in that list.
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
CREATE TABLE #Abundant (i INT PRIMARY KEY NOT NULL)
; WITH Ten(i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Ten
WHERE i < 9
)
INSERT INTO #Integers (i)
SELECT 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i + 1
FROM Ten o
CROSS JOIN Ten t
CROSS JOIN Ten h
CROSS JOIN Ten k
CROSS JOIN Ten k10
WHERE k10.i <= 2
AND 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i + 1 <= 28123
; WITH Abundant (i) AS
(
SELECT i1.i
FROM #Integers i1
CROSS APPLY
(
SELECT i
FROM #Integers i2
WHERE i1.i % i = 0
AND i < SQRT(i1.i) + 1
AND i < i1.i
UNION
SELECT i1.i / i
FROM #Integers i2
WHERE i1.i % i = 0
AND i < SQRT(i1.i) + 1
AND i > 1
) factors
GROUP BY i1.i
HAVING SUM(factors.i) > i1.i
)
INSERT INTO #Abundant
SELECT i
FROM Abundant
; WITH AbundantSums (j) AS
(
SELECT a1.i + a2.i
FROM #Abundant a1
INNER JOIN #Abundant a2
ON a1.i <= 28123 - a2.i
)
SELECT SUM(i)
FROM #Integers
WHERE i NOT IN (SELECT j FROM AbundantSums)
DROP TABLE #Integers
DROP TABLE #Abundant