Post date: Feb 08, 2015 3:37:30 AM
"How many continued fraction representation of square roots of numbers 10,000 and under have an odd repeating period?"
Building and parsing nested fractions is not fun in SQL. In fact, I'd guess that fractions are probably nasty in any programming language. Luckily Wikipedia had an almost decent formula. At the moment, it seems to have an error in the way it was written (Wikipedia is user content after all), but it only took a minor fix.
We just have to repeat this formula, storing the result in a table, until it hits a duplicate (already in the table).
CREATE FUNCTION dbo.GetContinuedFractionPeriod(@s int)
RETURNS INT
AS
BEGIN
DECLARE @m int = 0, @d int = 1, @a int = SQRT(@s), @result int
DECLARE @History TABLE (m INT NOT NULL, d INT NOT NULL, a INT NOT NULL, PRIMARY KEY (m, d, a))
-- The cleanest way to write this would be with try/catch. It would avoid both the IF statements.
-- But, sorry, can't use them in a function.
IF SQUARE(CONVERT(int,SQRT(@s))) = @s RETURN 0
WHILE 1 = 1
BEGIN
SELECT @m = @d * @a - @m
SELECT @d = 1.0 * (@s - SQUARE(@m)) / @d
SELECT @a = (SQRT(@s) + @m) / @d
INSERT INTO @History
SELECT @m, @d, @a
WHERE NOT EXISTS (SELECT 1 FROM @History WHERE m = @m AND d = @d AND a = @a)
IF @@ROWCOUNT = 0 BREAK
END -- While
SELECT @result = COUNT(*)
FROM @History
RETURN @result
END
GO
WITH Integers (i) AS
(
SELECT 2
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 10000
),
Periods (p) AS
(
SELECT dbo.GetContinuedFractionPeriod(i)
FROM Integers
)
SELECT COUNT(*)
FROM Periods
WHERE p > 0
AND p % 2 = 1
OPTION (MAXRECURSION 10000)
GO
DROP FUNCTION dbo.GetContinuedFractionPeriod
GO