Post date: Feb 20, 2015 1:0:58 AM
"Calculate the continued fraction representation of e (expressed as [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]) and find the 100th convergent. What is the sum of the digits in the numerator (for the web form)?"
It took a bit searching to find the method to calculate convergents for e. The closest thing I could find was how to converge using an entirely decimal representation, which doesn't help because Project Euler wants fractions. The question provides the first 10 in the series, but it's not such a simple series that I could write a program based on 10 samples.
But I found a nice method in the source code for Sage.
Problem 2 is that after the 71st term, the numbers overflow all SQL Server numeric types. So it's time to dust off the functions for string addition AND string multiplication. Ew. All in all, I'm using 4 user-defined functions, which we have seen before.
CREATE FUNCTION dbo.ShiftStringRight
(
@String varchar(max), @Places int
)
...
GO
CREATE FUNCTION dbo.AddBigNumbers
(
@Number1 varchar(max), @Number2 varchar(max)
)
...
GO
CREATE FUNCTION dbo.MultiplyBigNumbers (@Number1 varchar(max), @Number2 varchar(max))
...
GO
CREATE FUNCTION dbo.SumDigits (@Number varchar(1000))
...
GO
-- Now we can get down to answering the problem.
DECLARE @id int, @i VARCHAR(100)
-- Populate the continued fraction sequence with the first 100 entries in the sequence [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 2k, 1, ...]
CREATE TABLE #Shorthand (id INT IDENTITY(1,1) PRIMARY KEY NOT NULL, i VARCHAR(100) NOT NULL)
INSERT INTO #Shorthand (i) VALUES (2)
; WITH Integers (i) AS
(
SELECT 2
UNION ALL
SELECT i + 2
FROM Integers
WHERE i < 100
),
Loops (j, k) AS
(
SELECT 1, 0
UNION SELECT 2, 1
UNION SELECT 3, 0
),
eSequence (i, ctr) AS
(
SELECT POWER(i.i,l.k), ROW_NUMBER() OVER (ORDER BY i.i, l.j)
FROM Integers i
CROSS JOIN Loops l
)
INSERT INTO #Shorthand (i)
SELECT i
FROM eSequence
WHERE ctr <= 99
ORDER BY ctr
-- This is the result table. It starts with two rows, which are used to calculate the first new row that is added, but which are not returned.
-- Putting them in the same query makes populating the table a very clean query, without any special cases.
CREATE TABLE #Fractions (id INT IDENTITY(1,1) PRIMARY KEY NOT NULL, n VARCHAR(100) NOT NULL, d VARCHAR(100) NOT NULL)
INSERT INTO #Fractions (n, d) VALUES (0, 1), (1, 0)
-- Process each record in the convergents sequence table.
DECLARE ConvergencyCursor CURSOR LOCAL FOR
SELECT id, i
FROM #Shorthand
ORDER BY id
OPEN ConvergencyCursor
WHILE 1 = 1 BEGIN
FETCH NEXT FROM ConvergencyCursor INTO @id, @i
IF @@FETCH_STATUS <> 0 BREAK
INSERT INTO #Fractions (n, d)
SELECT dbo.AddBigNumbers(dbo.MultiplyBigNumbers(f1.n, @i), f.n) -- f1.n * @i + f.n
, dbo.AddbigNumbers(dbo.MultiplyBigNumbers(f1.d, @i), f.d) -- f1.d * @i + f.d
FROM #Fractions f
CROSS JOIN #Fractions f1
WHERE f.id = @id
AND f1.id = @id + 1
END -- ConvergencyCursor
CLOSE ConvergencyCursor
DEALLOCATE ConvergencyCursor
SELECT TOP 1 dbo.SumDigits(n)
FROM #Fractions
WHERE id > 2
ORDER BY id DESC
DROP TABLE #Shorthand
DROP TABLE #Fractions
GO
DROP FUNCTION dbo.ShiftStringRight
GO
DROP FUNCTION dbo.AddBigNumbers
GO
DROP FUNCTION dbo.MultiplyBigNumbers
GO
DROP FUNCTION dbo.SumDigits
GO