Post date: Apr 19, 2015 1:3:57 AM
"Of the fractions n/d in the series where d is less than or equal to 1 million, n is less than d and greater than 0, and the highest common factor is 1 (a reduced proper fraction), what is the greatest fraction whose value is less than 3/7? Return the numerator of this fraction."
What do we know? We know the answer is between 2/7 and 3/7. The answer is close to 3/7. The numerator is less than 3/7 of the denominator.
The smallest difference would be the one where the difference between the two numerators is 1, and the denominator is biggest. Consider 2/7. 2 is 1 less than 3. Now multiply 7 times 2. 5/14 is less than 6/14, and the difference is less than 2/7, because the denominator is larger. We don't need to check 4/14 because we know it's a bad answer. So we multiply 2/7 by each integer, subtract 1 from the numerator, and save. Do this for the full series. Then work from the top, throwing out everything where GCD isn't 1. As soon as you hit a reduced proper fraction, stop, because you have the answer.
I used a bunch of optimizations but didn't really need them. But I just glanced ahead at 72. Basically the same problem but they want to calculate every single value up to a million. That cuts out that limit of 3/7 and means it will take FOREVER, and my optimizations are out the window. I won't be able to use this method on that problem. /me feels slightly troubled.
CREATE FUNCTION dbo.BinaryGCD(@a int, @b int)
RETURNS INT
AS
BEGIN
-- SQL Server has a maximum recursion depth of 32, which is tiny.
-- But we can fake it, because we aren't combining child results with parent results. We are just resetting all the values and recalculating.
-- Once we get a solution, that breaks entirely out of the loop
DECLARE @d INT = 1
WHILE 1 = 1
BEGIN
IF @a = 1 OR @b = 1
RETURN @d
ELSE IF @b % @a = 0
RETURN @a
ELSE IF @a % @b = 0
RETURN @b
ELSE IF @a = @b
RETURN @a
ELSE IF @a % 2 = 0 AND @b % 2 = 0
SELECT @a = @a/2, @b = @b/2, @d = 2 * @d
ELSE IF @a % 2 = 0
SELECT @a = @a/2
ELSE IF @b % 2 = 0
SELECT @b = @b/2
ELSE IF @b > @a
SELECT @b = (@b - @a)/2, @d = 1 -- Fake recursion
ELSE IF @a > @b
SELECT @a = (@a - @b)/2, @d = 1 -- Fake recursion
END -- While
RETURN @d
END
GO
-- If both are even, then the GCD is 2, which means it violates the problem criteria. So it is important to split out evens and odds.
CREATE TABLE #Evens (i BIGINT PRIMARY KEY NOT NULL)
CREATE TABLE #Odds (i BIGINT PRIMARY KEY NOT NULL)
INSERT INTO #Odds VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers (i) AS
(
SELECT o.i +
10 * d.i +
100 * h.i +
1000 * k.i +
10000 * k10.i +
100000 * k100.i +
1
FROM #Odds o
CROSS JOIN #Odds d
CROSS JOIN #Odds h
CROSS JOIN #Odds k
CROSS JOIN #Odds k10
CROSS JOIN #Odds k100
)
INSERT INTO #Odds
SELECT i
FROM Integers
WHERE i > 9
DELETE FROM #Odds WHERE i = 0
-- Turn the Odds table into an actual odds table and a corresponding evens table
DELETE
FROM #Odds
OUTPUT deleted.i
INTO #Evens
WHERE i % 2 = 0
CREATE TABLE #Fractions (n INTEGER NOT NULL, d INTEGER NOT NULL, GCDChecked bit NOT NULL DEFAULT 0)
DECLARE @d int = 1000000, @minn int = 2, @mind int = 7
WHILE @d >= 0
BEGIN
INSERT INTO #Fractions (n, d)
SELECT n.i AS n, d.i AS d
FROM #Evens n
INNER JOIN #Odds d ON n.i < d.i
WHERE 7 * n.i < 3 * d.i -- Less than 3/7
AND @mind * n.i > @minn * d.i -- Each time I check, I don't need to check below that any more.
AND 100000 * n.i BETWEEN 42857 * d.i AND 42858 * d.i -- Around .45287
AND n.i <= 428570 -- Highest 3/7 possible
AND (3 * d.i) - (7 * n.i) = 1 -- Closest to the next multiple of 3/7
AND d.i = @d
INSERT INTO #Fractions (n, d)
SELECT n.i AS n, d.i AS d
FROM #Odds n
INNER JOIN #Evens d ON n.i < d.i
WHERE 7 * n.i < 3 * d.i -- Less than 3/7
AND @mind * n.i > @minn * d.i -- Each time I check, I don't need to check below that any more.
AND 100000 * n.i BETWEEN 42857 * d.i AND 42858 * d.i -- Around .45287
AND n.i <= 428570 -- Highest 3/7 possible
AND (3 * d.i) - (7 * n.i) = 1 -- Closest to the next multiple of 3/7
AND d.i = @d
INSERT INTO #Fractions (n, d)
SELECT n.i AS n, d.i AS d
FROM #Odds n
INNER JOIN #Odds d ON n.i < d.i
WHERE 7 * n.i < 3 * d.i -- Less than 3/7
AND @mind * n.i > @minn * d.i -- Each time I check, I don't need to check below that any more.
AND 100000 * n.i BETWEEN 42857 * d.i AND 42858 * d.i -- Around .45287
AND n.i <= 428570 -- Highest 3/7 possible
AND (3 * d.i) - (7 * n.i) = 1 -- Closest to the next multiple of 3/7
AND d.i = @d
-- Do the GCD check, which we delayed until applying.
DELETE FROM #Fractions
WHERE dbo.BinaryGCD(n, d) > 1
AND GCDChecked = 0
-- The first record added happens to be the answer so let's short circuit the process
IF EXISTS (SELECT 1 FROM #Fractions) BREAK
UPDATE #Fractions SET GCDChecked = 1 WHERE GCDChecked = 0
-- We started out filtering out everything below 2/7, which was obviously going to be a lot less than 3/7.
-- But once we start capturing data, we can filter out the highest value we have, because unless it is higher, it's useless.
-- Now it turns out the answer is the number just barely under the highest multiple of 7,
SELECT TOP (1) @minn = n, @mind = d
FROM #Fractions
ORDER BY 1.0 * n/d DESC
SET @d = @d - 1
-- Make the table smaller, so calculations get faster
DELETE FROM #Odds WHERE i > @d
DELETE FROM #Evens WHERE i > @d
END
SELECT TOP 1 n, d FROM #Fractions ORDER BY 1.0 * n/d DESC
DROP TABLE #Evens
DROP TABLE #Odds
DROP TABLE #Fractions
GO
DROP FUNCTION BinaryGCD
GO