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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s