Post date: Oct 18, 2014 12:2:58 AM
"What are the last 10 digits of the result of the series 1**1 + 2**2 + 3**3 + ... + n**n where n = 1000?"
Because we are in SQL Server, we can't use one line to return the answer instantly. It really is a trivial problem with a one line solution ... str(sum([x ** x for x in range(1,1000)]))[-10:] ... except that the language must support large numbers. I wonder if there's any way I could run that in SQL server ... something to think of.
To do it in SQL, we must take advantage of the fact that we don't care about any digits left of the 10th. The problem only asks for the last 10 digits. The last 10 digits of 2 * 69 are the same as 10000000002 * 69. And if you mulitply it by 69 again, the last 10 digits are the same whether you multiplied 138 or 690000000138.
CREATE TABLE #Integers (i BIGINT PRIMARY KEY NOT NULL)
; WITH Integers (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 999 -- Note: We don't care about 1000, or any power of 10 actually, because they provide 0 in the last 10 digits.
)
INSERT INTO #Integers
SELECT i
FROM Integers
OPTION (MAXRECURSION 1000)
-- This little recursive query returns i ** 1, i ** 2, i ** 3, ... i ** n
-- Except notice that each result is the result mod 10000000000, which drops off everything to the left of the last 10 digits.
; WITH Multiply (i, pow, result) AS
(
SELECT i.i, 0, CONVERT(bigint,1)
FROM #Integers i
UNION ALL
SELECT i.i, m.pow + 1, CONVERT(bigint,i.i * m.result % 10000000000)
FROM #Integers i
INNER JOIN Multiply m
ON m.i = i.i
WHERE m.pow + 1 <= i.i
)
SELECT SUM(result) % 10000000000
FROM Multiply
WHERE i = pow
OPTION (MAXRECURSION 1000)
DROP TABLE #Integers