Post date: Jun 10, 2018 12:6:42 PM
"Find the longest amicable chain with no element over one million and return its smallest element."
Now this is a pain to describe. For each number under 1 million, sum up all the divisors, excluding the number itself, getting another number. If the new number is the starting number, stop, or else repeat on the new number.
CREATE TABLE #Integers (i INT NOT NULL PRIMARY KEY)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers (i) AS
(
SELECT i.i +
10 * j.i +
100 * h.i +
1000 * s.i +
10000 * m.i +
100000 * jm.i
FROM #Integers i
CROSS JOIN #Integers j
CROSS JOIN #Integers h
CROSS JOIN #Integers s
CROSS JOIN #Integers m
CROSS JOIN #Integers jm
WHERE jm.i < 5
)
INSERT INTO #Integers
SELECT i + 1
FROM Integers
WHERE i >= 9
DELETE FROM #Integers
WHERE i < 2
CREATE TABLE #Factors (n INT NOT NULL, f INT NOT NULL, PRIMARY KEY (n, f))
-- Brute force it like the brute squad. But only do the math at the start. After that, only recursively join.
-- Build up a table of factors from the bottom, deleting records from the source table as you go, so it becomes smaller and faster.
-- This is faster than working from the top to the bottom by dividing, which is very slow.
-- There are multiple ways that a chain can end.
-- One way to end is to hit a prime, or a number that eventually leads to a prime.
-- This factor table is a modified version. It doesn't include 1, which is fluff, and doesn't include primes, which all instantly link to 1 and get stuck.
DECLARE @divisor int = 2
WHILE @divisor < SQRT(1000000) + 1
BEGIN
INSERT INTO #Factors
SELECT i * @divisor, @divisor
FROM #Integers
SET @divisor = @divisor + 1
DELETE FROM #Integers
WHERE i > 1000000.0/@divisor
END
INSERT INTO #Factors
SELECT n, n/f
FROM #Factors
EXCEPT
SELECT n, f
FROM #Factors
CREATE TABLE #Links (n INT PRIMARY KEY NOT NULL, link INT NOT NULL)
INSERT INTO #Links
SELECT n, SUM(f) + 1
FROM #Factors
GROUP BY n
-- We are only interested in cases that loop back to themselves at the start. Even if there is a 101 number chain, if it ends at 41 (a prime), it doesn't count.
-- We can GREATLY improve processing speed by getting rid of useless numbers, that don't link into the chain (we already removed primes). From 15 minutes to 15 seconds.
WHILE 1 = 1
BEGIN
DELETE FROM #Links
WHERE NOT EXISTS (SELECT 1
FROM #Links l2
WHERE l2.n = #Links.link)
IF @@ROWCOUNT = 0 BREAK
END
-- This chain has no handling to tell the difference between a chain that ends because it hits a prime and one that ends because it loops back.
-- The longest chain is one that loops back, so the prime case doesn't need to be tested.
-- To track back the entire history for loops, we need some way to store the history. Because you can't write a where clause on previous rows. So we use a string.
-- This is slow but with the dead chains gone, not too bad, really. Under 20s.
; WITH Recurse AS
(
SELECT n AS start, n, link, 2 AS numbers, CONVERT(varchar(max),CONCAT(n, '-', link)) AS chain, 0 AS amicable
FROM #Links
WHERE n <> link -- Filter out perfect numbers, just because.
UNION ALL
SELECT p.start, n.n, n.link, p.numbers + 1
, CONVERT(varchar(max),CONCAT(p.chain, '-', n.link)) AS chain
, CASE WHEN p.start = a.link THEN 1 ELSE 0 END AS amicable
FROM Recurse p
INNER JOIN #Links n
ON n.n = p.link
-- Look ahead for amicability, in the step that is a duplicate. This only works because we know the chain length is over 4. The problem gives us a case with 5.
INNER JOIN #Links a
ON a.n = n.link
WHERE p.start <> n.link -- Stop when we hit the starting number.
AND n.n <> n.link -- Stop when we hit a perfect number (itself), which will loop forever.
AND p.chain NOT LIKE CONCAT('%-', n.link, '-%') -- Stop when we hit a number already in this chain, for the same reason
),
-- We don't know it's amicable until we hit the end.
AmicableChains AS
(
SELECT start, numbers
FROM Recurse
WHERE amicable = 1
)
SELECT TOP (1) start
FROM AmicableChains
ORDER BY numbers DESC, start
OPTION (MAXRECURSION 32767)
DROP TABLE #Factors
DROP TABLE #Integers
DROP TABLE #Links