Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
That is a great answer, it gave me the push in the back to find the answer. Thanks a lot for your time. –  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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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