Post date: Jul 16, 2017 11:41:41 AM
"For every positive integer below 10 million, sum the square of its digits, and then repeat this operation on the new number, until the result is 1 or 89. How many are 89?"
Apparently these are called 'happy numbers' and 'sad numbers.' https://en.wikipedia.org/wiki/Happy_numbers
The important point is that if a number is happy, all numbers of its sequence (the recursive process described) are happy. If any are sad, all are sad. But the wikipedia page doesn't give any shortcuts for detecting happy numbers aside from doing the math and checking, which is slow.
My first thought was to memoize the list, because once you encounter an item in the list, you know the answer. The problem is that it's too big to memoize. 10 million numbers are slow in SQL, even if you do not calculations at all. So then I decided to try partial memoization.
The biggest number under 10 million, 9999999, is 81 (9 squared) times 7 digits, 567, which is well under 1000. And the next number in that series is 110, a much smaller number. In fact, all the numbers above 99 have next numbers that are always smaller. If the number is smaller, then if we have a memoized list, it will be in it. So I need to build a memo of 600 numbers (takes under 1 second), and then join to that.
It takes longer than I would prefer, because even a simple lookup on 10 million numbers takes time, but it's not bad.
CREATE TABLE #Digits (i INT PRIMARY KEY NOT NULL)
INSERT INTO #Digits VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
CREATE TABLE #Memomemo (i INT PRIMARY KEY NOT NULL, n INT NOT NULL, happy BIT NULL)
-- Fill a list with integers up to 600 and the sum of the squares of its digits
INSERT INTO #Memomemo (i, n)
SELECT 100 * h.i +
10 * d.i +
o.i,
h.i * h.i +
d.i * d.i +
o.i * o.i
FROM #Digits o
CROSS JOIN #Digits d
CROSS JOIN #Digits h
WHERE h.i < 6
-- We know that 1, 10, 100, etc (the 0s don't affect the result) are happy. We know that 89 is sad. Every sad number includes 89 in its series.
-- So if we recursively join this list to itself, it is possible to very easily populate the entire list, without repeated calculation.
DELETE FROM #Memomemo WHERE i = 0
UPDATE #Memomemo
SET happy = 1
WHERE i IN (1, 10, 100)
UPDATE #Memomemo
SET happy = 0
WHERE i IN (4, 16, 37, 58, 89, 145, 42, 20)
-- Join each number to the next number in its series. The happy/sad value is the same.
-- Keep doing this until you've captured each one. This is a recursive process.
WHILE 1 = 1
BEGIN
UPDATE m1
SET happy = m2.happy
FROM #Memomemo m1
INNER JOIN #Memomemo m2
ON m2.i = m1.n
WHERE m1.happy IS NULL
AND m2.happy IS NOT NULL
IF @@ROWCOUNT = 0 BREAK
END
-- Table with 10 million integers and their next #. Takes storage but is still faster than querying on a CTE.
; WITH TenMillion (i, n) AS
(
SELECT 1000000 * m.i +
100000 * k100.i +
10000 * k10.i +
1000 * k.i +
100 * h.i +
10 * d.i +
o.i,
m.i * m.i +
k100.i * k100.i +
k10.i * k10.i +
k.i * k.i +
h.i * h.i +
d.i * d.i +
o.i * o.i
FROM #Digits o
CROSS JOIN #Digits d
CROSS JOIN #Digits h
CROSS JOIN #Digits k
CROSS JOIN #Digits k10
CROSS JOIN #Digits k100
CROSS JOIN #Digits m
)
SELECT *
INTO #TenMillion
FROM TenMillion
-- It's faster to count the happy numbers (fewer of them) and then subtract.
SELECT 9999999 - COUNT(DISTINCT tm.i)
FROM #TenMillion tm
INNER JOIN #Memomemo m
ON m.i = tm.n
WHERE m.happy = 1
DROP TABLE #MemoMemo
DROP TABLE #Digits
DROP TABLE #TenMillion