# Euler Problem 243 – Always the Totient OK, so I had to look up the answer to this one. In my defence I did lots of research and determined that the resilience is related (once again) to Euler’s Totient function, specifically the relationship R(d) = phi(d)/(d-1). I figured that by using this relationship (and looking for R(d) lower than the ratio given) was the trick instead of having to brute force it. Nope. That is the brute force method. Ran for days and got nowhere.

So I broke down and looked up a solution. There aren’t very many for this one. Most were in interative languages like Ruby, which don’t help me. I did find one amazing solution is Haskell here, but for the life of me I don’t know why it works. I’ve adapted it and replaced as much as I can with clearer functions to help explain it. Perhaps not as efficient, but it still runs in less than a second.

Step One: Generate lists of primes and totients.
Step Two: Generate a list primorials consisting of tuples based on products of primes and totients.
Step Three: Use a recursive routine starting with the primorials list and a multiplier (m) of 1. If the current list head * m == the next primorial, then drop the head and loop. If the current list head * m is than the target then return it, otherwise increment m and loop.
Step Four: Shrug shoulders, open arms with palms upward, crinkle forehead, take a deep sign, and say, “WTF!”

``` import Data.List.Ordered primes :: [Integer] primes = 2 : sieve [3,5..] where sieve [] = [] sieve (p:xs) = p : sieve (xs `minus` [p*p, p*p+2*p..]) totient :: Integer -> Integer totient n = fromIntegral \$ length [x | x <- [1..n], gcd x n == 1] primorials :: [(Integer, Integer)] primorials = [(product \$ take x primes, product \$ map totient \$ take x primes) | x <- [1..]] findRes :: [(Integer, Integer)] -> Integer -> Integer findRes ((cpri,cphi):(npri,nphi):pps) m | cpri * m == npri = findRes ((npri,nphi):pps) 1 | fromIntegral (cphi * m) / fromIntegral ((cpri * m) - 1) < ratio = cpri * m | otherwise = findRes ((cpri,cphi):(npri,nphi):pps) (m + 1) where ratio = 15499/94744 main = print \$ findRes primorials 1 ```