Post date: Apr 13, 2015 11:26:7 PM
"What is the value of n under 10 million with the minimum value of n over Euler's totient of n where the digits in Euler's totient are a permutation of the digits in n. Do not include 1, which is equal to its own totient."
This problem is a minor tweak on the previous problem. The main thing that kills us is that the problem wants us to check numbers up to 10 million. 10 times the size. Problem 69 took 4.5 minutes to generate prime factors, so now it takes about 45 minutes. 4.5 was as fast as I could get it for 1 million, so I'm out of luck here.
So I had to go to the web and look for a faster solution. And I found that that the answer is not prime, because phi for a prime number isn't a permutation of that number. So it must be the problem with the fewest prime factors to be multiplied together, because each multiplication lowers the result of Euler's totient, which makes the overall value larger (n * (1 - (1/p1)) * (1 - (1/p2)) * ... * (1 - (1/pm)), remember). So it must be a number with exactly 2 prime factors. In addition, they should be as close together as possible, so both of the numbers must be pretty close to the square root of 10 million.
That's a MUCH smaller result set, 7s instead of 45 minutes.
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)
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
)
INSERT INTO #Integers
SELECT i + 1, SQRT(i+1)
FROM Integers
WHERE i >= 9
CREATE TABLE #Primes (i int not 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
CREATE TABLE #Factors (n INT NOT NULL, p INT NOT NULL, PRIMARY KEY (n, p))
INSERT INTO #Factors (n, p)
SELECT p1.i * p2.i, p1.i
FROM #Primes p1
INNER JOIN #Primes p2 ON p2.i <> p1.i
WHERE p1.i < 3163
AND CONVERT(bigint,p1.i) * CONVERT(bigint,p2.i) < 10000000
UNION
SELECT p1.i * p2.i, p2.i
FROM #Primes p1
INNER JOIN #Primes p2 ON p2.i <> p1.i
WHERE p1.i < 3163
AND CONVERT(bigint,p1.i) * CONVERT(bigint,p2.i) < 10000000
-- Euler's Totient is n * (1 - (1/p1)) * (1 - (1/p2)) * ... * (1 - (1/pm)) where p1 to pm are the prime factors of n
; WITH PhiNPhi (n, phi, nphi) AS
(
SELECT n, n * EXP(SUM(LOG(1 - (1.0/p)))), 1/EXP(SUM(LOG(1 - (1.0/p))))
FROM #Factors
WHERE p < n
GROUP BY n
UNION
SELECT n, n * (1 - (1.0/p)) , 1/(1 - (1.0/p))
FROM #Factors
WHERE p = n
AND p > 1
)
SELECT n, CONVERT(bigint,phi) AS phi, nphi
INTO #Totient
FROM PhiNPhi
WHERE LEN(n) = LEN(CONVERT(bigint,phi)) -- It can't be a permutation of the number of digits are different.
-- A permutation will have the same count of each digit in the results.
-- (This, and many other Euler problems, would be nicer if SQL Server had a function that would sort the characters in a string).
; WITH Results AS
(
SELECT n, phi, nphi
, LEN(n) - LEN(REPLACE(n,'0','')) AS c0
, LEN(n) - LEN(REPLACE(n,'1','')) AS c1
, LEN(n) - LEN(REPLACE(n,'2','')) AS c2
, LEN(n) - LEN(REPLACE(n,'3','')) AS c3
, LEN(n) - LEN(REPLACE(n,'4','')) AS c4
, LEN(n) - LEN(REPLACE(n,'5','')) AS c5
, LEN(n) - LEN(REPLACE(n,'6','')) AS c6
, LEN(n) - LEN(REPLACE(n,'7','')) AS c7
, LEN(n) - LEN(REPLACE(n,'8','')) AS c8
, LEN(n) - LEN(REPLACE(n,'9','')) AS c9
, LEN(phi) - LEN(REPLACE(phi,'0','')) AS p0
, LEN(phi) - LEN(REPLACE(phi,'1','')) AS p1
, LEN(phi) - LEN(REPLACE(phi,'2','')) AS p2
, LEN(phi) - LEN(REPLACE(phi,'3','')) AS p3
, LEN(phi) - LEN(REPLACE(phi,'4','')) AS p4
, LEN(phi) - LEN(REPLACE(phi,'5','')) AS p5
, LEN(phi) - LEN(REPLACE(phi,'6','')) AS p6
, LEN(phi) - LEN(REPLACE(phi,'7','')) AS p7
, LEN(phi) - LEN(REPLACE(phi,'8','')) AS p8
, LEN(phi) - LEN(REPLACE(phi,'9','')) AS p9
FROM #Totient
)
SELECT TOP 1 n
FROM Results
WHERE c0 = p0 AND c1 = p1 AND c2 = p2 AND c3 = p3 AND c4 = p4 AND c5 = p5
AND c6 = p6 AND c7 = p7 AND c8 = p8 AND c9 = p9
ORDER BY nphi
DROP TABLE #Integers
DROP TABLE #Primes
DROP TABLE #Factors
DROP TABLE #Totient