5
$\begingroup$

I am working on challenge 243 from Project Euler (PE 243). The question is:

$\text{Solve } \phi (n) < (n-1)\cdot \frac{15499}{94744}$

I can calculate $\phi(n)$ for any $n$, but I think the $n$ which solves the problem is larger than the range I can brute force. I have never before worked with $\phi(n)$ before, but I'd love to learn how to solve this kind of problem.

Research on Google gave me definitions of $\phi(n)$, which I already know, but nothing to help me solve the problem. If you could give me any tips in the right direction, and NOT the answer. Thanks in advance.


Edit: I found a clue: $\phi(n) \ge \sqrt{n}$ This should give me a limit where $n$ will always give me a number larger than the desired result. I'm working on it.

  • 0
    @MarkBennet I got that part covered. Thanks so far for all the input, I'm coming somewhere.2012-08-11

2 Answers 2

6

Some information that may be useful: Let $n$ have prime power decomposition $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$ where the $p_i$ are distinct primes. Then $\varphi(n)=(p_1-1)p_1^{a_1-1}(p_2-1)p_2^{a_2-1}\cdots (p_k-1)p_k^{a_k-1}.$ (For details about the $\varphi$-function, see this.) By using the above formula for $\varphi(n)$, we can see that $\frac{\varphi(n)}{n-1}=\frac{n}{n-1}\frac{\varphi(n)}{n}=\frac{n}{n-1}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right).$ So to make $\varphi/(n-1)$ smallish "cheaply" it is good to use small primes, all to the first power. Decorating the primes with powers $a_i$ greater than $1$ has only a minor effect on the ratio.

  • 0
    That is a great answer, it gave me the push in the back to find the answer. Thanks a lot for your time.2012-08-11
2

For $\displaystyle n=\prod p_i^{e_i}$

we have that $\phi(n)=n\prod \left(1-\frac1 p_i\right)$

so to get small $\dfrac{\phi(n)}n$ you want lots of small prime factors, $n=2\cdot3\cdot5\cdots$