Post date: May 09, 2015 10:29:25 PM
"How many fractions n/d are there in the series where d is between 0 and 12000, n is less than d and greater than 0, the highest common factor is 1 (a reduced proper fraction), and the result is between 1/3 and 1/2?"
Can't use Totient here because it's a filtered list we need to sum. I don't think I can just filter the list of factors. It's unlikely that the function will return good data. The problem creators understood this and made the upper bound a lot smaller. With this, I found it faster to do this entirely in memory, step by step, rather than a setwise solution.
(Man, these proper fraction problems are really wearing on me.)
CREATE FUNCTION dbo.IsProper(@a int, @b int)
RETURNS BIT
AS
BEGIN
IF @a = 1 OR @b = 1
RETURN 1
ELSE IF @a % @b = 0
RETURN 0
ELSE IF @b % @a = 0
RETURN 0
WHILE 1 = 1
BEGIN
IF @a = 1 OR @b = 1
RETURN 1
ELSE IF @a = @b
RETURN 0
ELSE IF @a % 2 = 0 AND @b % 2 = 0
RETURN 0
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
ELSE IF @a > @b
SELECT @a = (@a - @b)/2
END
RETURN 1
END
GO
-- Not many shortcuts here. Just power through.
DECLARE @n int = 1, @d int = 2, @result bigint = 0
WHILE @d <= 12000
BEGIN
-- Provide a boost of speed by not checking these numbers that are obviously too small
-- This rounds down rather than up. I could make it round up but occasionally something slips by because of the rounding.
-- Doing it this way makes a process with only integer multiplication processes anywhere it is important. That's nice. And the runtime is the same.
SET @n = @d/3.00000000
-- Check until n/d < 1/2
WHILE 2 * @n < @d
BEGIN
-- Check if GCD is 1 only if n/d > 2/3.
IF 3 * @n > @d
IF dbo.IsProper(@n, @d) = 1
SET @result = @result + 1
-- If d is even, then we should not look at any even n. Two evens have 2 as a factor.
IF @d % 2 = 0 AND @n % 2 <> 0
SET @n = @n + 2
ELSE
SET @n = @n + 1
END -- n/d < 1/2
SET @d = @d + 1
END -- d < 12000
SELECT @result
GO
DROP FUNCTION dbo.IsProper
GO