La resolución de $\phi (n) < (n-1) \cdot \frac{15499}{94744} $

Question

Estoy trabajando en el desafío 243 de Project Euler (PE 243). La pregunta es:

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

Puedo calcular el $\phi(n)$ cualquier $n$, pero creo que el $n$ que resuelve el problema es mayor que el intervalo puedo fuerza bruta. Nunca antes he trabajado con $\phi(n)$ antes, pero me encantaría aprender a resolver este tipo de problema.

La investigación en Google me dio definiciones de $\phi(n)$, que ya conozco, pero nada que me ayude a resolver el problema. Si usted me podría dar algún consejo en la dirección correcta, y NO la respuesta. Gracias de antemano.

---

Edit: he encontrado una pista: $\phi(n) \ge \sqrt{n}$ Este debe darme un límite donde $n$ siempre me dan un número mayor que el resultado deseado. Estoy trabajando en ello.

Answer 1

Alguna información que puede ser útil: Vamos a $n$ primer poder de la descomposición $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$ donde el $p_i$ son distintos de los números primos. Entonces $$\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}.$$ (Para los detalles acerca de la $\varphi$-función, vea esto.) Utilizando la fórmula anterior para $\varphi(n)$, podemos ver que $$\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).$$ Así que, para $\varphi/(n-1)$ pequeña "barato" es bueno para el uso de pequeños primos, todos a la primera potencia. La decoración de los números primos con potencias $a_i$ mayor que $1$ tiene sólo un efecto menor en la relación.

Answer 2

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

tenemos que $$\phi(n)=n\prod \left(1-\frac1 p_i\right)$$

así que para obtener pequeño $\dfrac{\phi(n)}n$ desea un montón de pequeños factores primos, $n=2\cdot3\cdot5\cdots$