Post date: Apr 11, 2015 11:39:38 PM
"What value of n less than or equal to 1 million gives a maximum value of n divided by Euler's totient of n (the quantity of numbers less than n that are relatively prime to n)?"
While calculating relative primes takes too long, Euler's totient has an easy formula. Once you have the prime factors, it's quick to calculate. The fastest way I found to get the prime factors was a combination of brute force (first part) and simple lookup and insert (second part). It takes 3 mins, but beats every other method I looked at, including Fermat's (note: I didn't look at other one-by-one methods).
First I grab all the primes, all the prime factors under the square root of n, and the n/p for those same records where n/p is prime. The only records left are n/p where n/p is not prime. Now it so happens that we already have that data. n/p is already in the table, having been written during the first step. For example, if you need calculate 2 and 9 as factors of 18, if you already have the prime factors of 9 (3), you just need to copy them to 18. No need to re-calculate. We just need to repeatedly go through the table, copying back the numbers already calculated, recursively, until we have it all.
CREATE TABLE #Integers (i int not null primary key, r money not null)
INSERT INTO #Integers VALUES (0, 0), (1, 1), (2, SQRT(2)), (3, SQRT(3)), (4, 2), (5, SQRT(5)), (6, SQRT(6)), (7, SQRT(7)), (8, SQRT(8)), (9, 3)
; WITH Integers(i) AS
(
SELECT 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 + 1, SQRT(i+1)
FROM Integers
WHERE i >= 9
-- Build a table of primes.
CREATE TABLE #Primes (i intnot null primary key)
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
-- Load a table of distinct prime factors.
CREATE TABLE #Factors (n INT NOT NULL, p INT NOT NULL, PRIMARY KEY (n, p))
CREATE UNIQUE INDEX IX_Factor_DropDups ON #Factors (n, p) WITH IGNORE_DUP_KEY
-- Primes are their only factors.
INSERT INTO #Factors (n, p)
SELECT i.i, i.i
FROM #Integers i
WHERE i.i IN (SELECT i FROM #Primes)
-- Simple factors of non-primes.
INSERT INTO #Factors (n, p)
SELECT i.i, p.i
FROM #Integers i
INNER JOIN #Primes p ON p.i <= i.r AND i.i % p.i = 0
WHERE i.i NOT IN (SELECT i FROM #Primes)
-- Other side of simple factors of non-primes.
INSERT INTO #Factors (n, p)
SELECT i.i, i.i/p.i
FROM #Integers i
INNER JOIN #Primes p ON p.i <= i.r AND i.i % p.i = 0
WHERE i.i NOT IN (SELECT i FROM #Primes)
AND i.i/p.i IN (SELECT i FROM #Primes)
-- Factors of factors.
WHILE 1 = 1
BEGIN
INSERT INTO #Factors
SELECT DISTINCT f.n, f2.p
FROM #Factors f
INNER JOIN #Factors f2 ON f2.n = f.n/f.p
WHERE f.n NOT IN (SELECT i FROM #Primes)
AND f.n/f.p NOT IN (SELECT i FROM #Primes)
IF @@ROWCOUNT = 0 BREAK
END -- WHILE
-- Euler's Totient is n * (1 - (1/p1)) * (1 - (1/p2)) * ... * (1 - (1/pm)) where p1 to pm are the prime factors of n
-- This problem asks for n/phi, which is 1/(everthing to the right of n). n is cancelled out.
; WITH PhiNPhi (n, nphi) AS
(
SELECT n, 1/EXP(SUM(LOG(1 - (1.0/p))))
FROM #Factors
WHERE p < n
GROUP BY n
UNION
SELECT n, 1/(1 - (1.0/p))
FROM #Factors
WHERE p = n
AND p > 1
)
SELECT TOP 1 n
FROM PhiNPhi
ORDER BY nphi DESC
DROP TABLE #Integers
DROP TABLE #Primes
DROP TABLE #Factors