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

### Like this:

Like Loading...

*Related*