Post date: May 23, 2014 1:9:41 AM
"Of the sequence of numbers found by adding the positive integers (1, 1 + 2, 1 + 2 + 3, etc), what is the first number to have over 500 divisors?"
I have two solutions for this, one that works in general and one that requires SQL Server 2012 or higher. On older versions of SQL Server, you can't generate a running total (the sequence) efficiently for thousands of numbers, so it's necessary to step through, doing each number one by one. Not a proper SQL solution, but fast.
CREATE TABLE #Integers (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
INSERT INTO #Integers (i)
SELECT 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Integers o
CROSS JOIN #Integers t
CROSS JOIN #Integers h
CROSS JOIN #Integers k
WHERE 1000 * k.i + 100 * h.i + 10 * t.i + o.i > 9
DELETE FROM #Integers WHERE i = 0
DECLARE @c int = 1, @triangle int = 0, @count int
-- Do each number, adding the sequence of natural numbers (@c) to the running total (@triangle).
-- Then count the number of factors. Remember, it's only necessary to calculate the first half of the list of factors, and then you can reverse it.
WHILE 1 = 1
BEGIN
SET @triangle = @triangle + @c
SET @c = @c + 1
; WITH Calc AS
(
SELECT i
FROM #Integers
WHERE @triangle % i = 0
AND i < SQRT(@triangle) + 1
UNION
SELECT @triangle / i
FROM #Integers
WHERE @triangle % i = 0
AND i < SQRT(@triangle) + 1
)
SELECT @count = COUNT(*)
FROM Calc
IF @count > 500
BREAK
END -- While
SELECT @triangle
DROP TABLE #Integers
Using new functions added with SQL Server 2012, you can efficiently calculate the running total without having to recalculate the entire list each time, like you need to do in older server versions. I like this version because it's a set-based solution, even though the syntax is wonky. Unfortunately, I have to cheat to use it. 10,000 numbers is not enough, and if I followed my pattern, I would then do 100,000. Well, that performs worse. But if you just go to 20,000, it performs better. I only know that the sequence is under 20,000 from solving the problem.
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
INSERT INTO #Integers (i)
SELECT 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i
FROM #Integers o
CROSS JOIN #Integers t
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
WHERE 10000 * k10.i + 1000 * k.i + 100 * h.i + 10 * t.i + o.i > 9
AND k10.i < 2
DELETE FROM #Integers WHERE i = 0
-- ROWS BETWEEN is a new feature. It totals only the rows previously calculated between the ones you specify.
; WITH Triangle AS
(
SELECT i, SUM(i) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS RunningTotal
FROM #Integers i
GROUP BY i
)
SELECT *
INTO #Triangle
FROM Triangle
SELECT TOP (1) t.RunningTotal
FROM #Triangle t
CROSS APPLY
(
SELECT i
FROM #Integers
WHERE t.RunningTotal % i = 0
AND i < SQRT(t.RunningTotal) + 1
UNION
SELECT t.RunningTotal / i
FROM #Integers
WHERE t.RunningTotal % i = 0
AND i < SQRT(t.RunningTotal) + 1
) factors
GROUP BY t.RunningTotal
HAVING COUNT(*) > 500
ORDER BY 1
DROP TABLE #Integers
DROP TABLE #Triangle