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
    I think you're supposed to find $\phi(n) < (n-1)*\frac{15499}{94744}$...2012-08-11
  • 0
    Very right, this is what I am calculating. Editing the question.2012-08-11
  • 0
    Try thinking about what sort of number will minimise $\frac{\phi(n)}{n-1}$.2012-08-11
  • 0
    You will find that $\frac{\phi(n)}{n}$ is quite easy to work with ...2012-08-11
  • 0
    http://math.stackexchange.com/questions/1016542012-08-11
  • 0
    I think also that there is a number which is very close to the bound and there is some computational delicacy required in establishing whether it meets the condition or not.2012-08-11
  • 0
    @MarkBennet I got that part covered. Thanks so far for all the input, I'm coming somewhere.2012-08-11

2 Answers 2

5

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$