Post date: Jul 11, 2015 3:36:38 PM
Back again after a two month break. That last batch of questions took a lot out of me, interest-wise.
"Every number, when you sum the factorial of its digits and then repeat the sum-factorial process, eventually produces a result that has already been calculated in the series, causing an infinite loop. How many starting numbers below 1 million produce a series of exactly terms before repeating numbers in the series?"
It's easy to eliminate the calculation from this ticket, which can be used up to speed up the process. All the values in integers to 1 million max out at 2177280, and all the intergers to 2177280 max out at 2177281. The factorial of 2177281 is a smaller number. This all means if we calculate all values to 2177281 and put them in a table, we will have all entries found in all the series from the beginning to the end. Factorial calculation becomes a basic lookup operation.
A large number of the series come from of the four values where the sum-factorial value equals the number itself. Obviously these aren't 60 long.
A few of them span chains that do not becme apparent until 3 or 4 factorials in the chain have been calculated. Finding these is the heaviest single operation needed.
The fastest solutions are based on knowledge of the answer. All the answers are for the same factorial (with one permutation) and the longest starting chain is length 4. But using these facts would be cheaing. Instead, I will create a table that will hold only the unique chains history, fill it with a million integers, and pick out the ones that would repeat. This adds half a minute but is not cheating.
An interesting fact is that there are only 5565 distinct factorial values. We can shave off a minute by collecting this list. But it does require more work shuffling updates around.
CREATE TABLE #Factorials (i INT PRIMARY KEY NOT NULL, f INT NOT NULL, circular BIT NOT NULL DEFAULT 0, c INT NOT NULL DEFAULT 0)
INSERT INTO #Factorials (i, f) VALUES (0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120), (6, 720), (7, 5040), (8, 40320), (9, 362880)
; WITH Milliontown (i, o, d, h, k, k10, k100, m) AS
(
SELECT o.i +
10 * d.i +
100 * h.i +
1000 * k.i +
10000 * k10.i +
100000 * k100.i +
1000000 * m.i,
o.f,
d.f,
h.f,
k.f,
k10.f,
k100.f,
m.f
FROM #Factorials o
CROSS JOIN #Factorials d
CROSS JOIN #Factorials h
CROSS JOIN #Factorials k
CROSS JOIN #Factorials k10
CROSS JOIN #Factorials k100
CROSS JOIN #Factorials m
WHERE m.i <= 2
)
INSERT INTO #Factorials (i, f)
SELECT i,
o +
CASE WHEN i < 10 THEN 0 ELSE d END +
CASE WHEN i < 100 THEN 0 ELSE h END +
CASE WHEN i < 1000 THEN 0 ELSE k END +
CASE WHEN i < 10000 THEN 0 ELSE k10 END +
CASE WHEN i < 100000 THEN 0 ELSE k100 END +
CASE WHEN i < 1000000 THEN 0 ELSE m END
FROM Milliontown
WHERE i BETWEEN 10 AND 2177281
-- This is a dump table that prevents any repeating chains from appearing.
-- It gets emptied as the process continues.
SELECT i, f
INTO #Integers
FROM #Factorials
WHERE i < 1000000
UPDATE #Factorials
SET circular = 1, c = 1
WHERE i = f
-- The number of distinct calculated values makes a much smaller table.
-- It is more work to keep both tables updated, but it pays off.
SELECT DISTINCT f AS i, circular
INTO #SmallFactorials
FROM #Factorials
CREATE TABLE #Bad (i INT NOT NULL)
DECLARE @ctr int
DECLARE @ctr2 INT = 1
WHILE 1 = 1
BEGIN
TRUNCATE TABLE #Bad
; WITH Bad(i) AS
(
SELECT i
FROM #Integers
GROUP BY i
HAVING COUNT(*) < @ctr2
)
INSERT INTO #Bad
SELECT i FROM Bad
IF EXISTS (SELECT 1 FROM #Bad)
BEGIN
UPDATE f
SET circular = 1, c = @ctr2 + 1
FROM #Bad i
INNER JOIN #Factorials f
ON f.i = i.i
WHERE i.i IN (SELECT i FROM #Bad)
UPDATE sm
SET circular = 1
FROM #SmallFactorials sm
INNER JOIN #Factorials f
ON sm.i = f.i
WHERE sm.circular = 0
AND f.circular = 1
-- Mark as bad all the records chaining from the latest
SET @ctr = @ctr2 + 1
WHILE 1 = 1
BEGIN
UPDATE f1
SET circular = 1, c = @ctr
FROM #Factorials f1
INNER JOIN #SmallFactorials f2
ON f2.i = f1.f
WHERE f1.circular = 0
AND f2.circular = 1
IF @@ROWCOUNT = 0 BREAK
UPDATE sm
SET circular = 1
FROM #SmallFactorials sm
INNER JOIN #Factorials f
ON sm.i = f.i
WHERE sm.circular = 0
AND f.circular = 1
SET @ctr = @ctr + 1
END
-- Clear out numbers that are known to be circular.
DELETE i
FROM #Integers i
INNER JOIN #Factorials f
ON i.i = f.i
WHERE f.circular = 1
IF NOT EXISTS (SELECT 1 FROM #Integers) BREAK
END -- If bad records exist
-- This is flawed, but for a reason.
-- It re-calculates (and throws out) the factorials for every row, even the ones that are already known.
-- It didn't save any time to look up only the end of the chain, so why waste the time.
INSERT INTO #Integers
SELECT i.i, f.f
FROM #Integers i
INNER JOIN #Factorials f
ON f.i = i.f
WHERE f.circular = 0
AND NOT EXISTS (SELECT 1
FROM #Integers i2
WHERE i2.i = i.i
AND i2.f = f.f)
SET @ctr2 = @ctr2 + 1
END -- While loop
SELECT COUNT(*) FROM #Factorials WHERE c = 60 AND i < 1000000
DROP TABLE #Factorials
DROP TABLE #Integers
DROP TABLE #SmallFactorials
DROP TABLE #Bad