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.

  • $\begingroup$ I think you're supposed to find $\phi(n) < (n-1)*\frac{15499}{94744}$... $\endgroup$ – Karolis Juodelė Aug 11 '12 at 13:13
  • $\begingroup$ Very right, this is what I am calculating. Editing the question. $\endgroup$ – Hidde Aug 11 '12 at 13:13
  • $\begingroup$ Try thinking about what sort of number will minimise $\frac{\phi(n)}{n-1}$. $\endgroup$ – Alex J Best Aug 11 '12 at 13:15
  • $\begingroup$ You will find that $\frac{\phi(n)}{n}$ is quite easy to work with ... $\endgroup$ – Mark Bennet Aug 11 '12 at 14:34
  • $\begingroup$ math.stackexchange.com/questions/101654 $\endgroup$ – sdcvvc Aug 11 '12 at 14:44

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.

  • $\begingroup$ That is a great answer, it gave me the push in the back to find the answer. Thanks a lot for your time. $\endgroup$ – Hidde Aug 11 '12 at 23:14

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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.