MathJax

SyntaxHighlighter

Highlight

Custom CSS

Thursday, May 23, 2013

Project Euler #69: Totient maximum

Here is a link to problem #69. Basically this problem serves as a gentle introduction to Euler's totient function. Just by looking at the definition you can get a hint about how to solve this problem.

Note that:

$$\phi(n) = n\prod_{p|n}(1 - \dfrac{1}{p})$$

...a proof of which can be found on the wikipedia page for the totient function.

Armed with that, we can consider maximizing this value:

$$\dfrac{n}{\phi(n)} = \dfrac{1}{\prod_{p|n}(1 - \dfrac{1}{p})}$$

It is plain to see that to maximize that ratio, we have to minimize the denominator. This will happen if there are a lot of $$p_{i}$$'s and each of them are very small, so basically we can hunt for this number by taking the product of the first few primes (a concept known as the primorial) such that the product is under 1000000.

As it turns out,

$$p_{7}\# = 510510 < 1000000$$ and $$p_{8}\# = 9699690 > 1000000$$

...so the number we want is 510510.
Post a Comment