Post date: Apr 26, 2015 9:11:8 PM
"How many fractions n/d are there 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)?"
(Look, I spelled WHERE correctly this time. Third most common words in SQL and I misspell it.)
Euler's Totient gives the number of numerators (n is less than and coprime with d) for each of the denominators. This is much faster than calculating GCD between 2 tables (up to 1 trillion values to check, so 30 days or more to calculate with all optimizations? um.....no). But it's still slow getting the prime factors.
It is faster to build up the entire table from the bottom, rather than counting down. What I do is take all the 2s and update everything that is a multiple of 2 (multiplying it by my table of integers). Then I do 3, 5, 7, 11, etc. Rather than doing a lot of division operations, I am doing just repeated multiplications. This is about 100X faster.
CREATE TABLE #Totient (n INT NOT NULL PRIMARY KEY, t NUMERIC(38,10) NOT NULL)
CREATE TABLE #Primes (i NUMERIC(38,10) not null primary key)
CREATE TABLE #Integers (i NUMERIC(38,10) not null primary key)
INSERT INTO #Integers VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT 1 + o.i +
10 * d.i +
100 * h.i +
1000 * k.i +
10000 * k10.i +
100000 * k100.i
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
)
INSERT INTO #Integers
SELECT i
FROM Integers
WHERE i > 9
DELETE FROM #Integers WHERE i < 2
-- Start with a list of primes.
INSERT INTO #Primes
SELECT i
FROM #Integers
WHERE i BETWEEN 2 AND 20
UNION
SELECT i
FROM #Integers
WHERE i > 20
AND i % 2 <> 0
AND i % 3 <> 0
AND i % 5 <> 0
AND i % 7 <> 0
AND i % 11 <> 0
AND i % 13 <> 0
AND i % 17 <> 0
AND i % 19 <> 0
DECLARE @num int = 1, @max int
SELECT @max = MAX(i)
FROM #Primes
WHILE 1 = 1
BEGIN
SELECT @num = MIN(i)
FROM #Primes
WHERE i > @num
IF @num > SQRT(@max)
BREAK
DELETE FROM #Primes
WHERE i % @num = 0
AND i > @num
END -- While
INSERT INTO #Totient
SELECT i, i - 1
FROM #Primes
INSERT INTO #Totient
SELECT i, i
FROM #Integers
WHERE i NOT IN (SELECT n FROM #Totient)
-- Calculate Euler's totient for multiples of each prime number.
DECLARE @d int = 1
WHILE 1 = 1 BEGIN
IF @d >= 999983 BREAK
SELECT @d = MIN(i)
FROM #Primes
WHERE i > @d
-- Save time by making the table smaller. We aren't concerned with values over 1 million, so as we multiply by greater numbers, we can take big numbers out of the table.
DELETE FROM #Integers
WHERE i > CEILING(1000000.0/@d) + 1
UPDATE t
SET t = t * (1 - 1.0/@d)
FROM #Totient t
INNER JOIN #Integers i
ON t.n = @d * i.i
END -- While
SELECT SUM(CONVERT(bigint,t)) FROM #Totient
DROP TABLE #Integers
DROP TABLE #Primes
DROP TABLE #Totient
GO