Desde $p \mid n \implies (p-1) \mid \varphi(n)$, $n$ $\varphi(n) \leqslant k$ no puede ser divisible por cualquier prime mayor que $k+1$. Además, la fórmula de $\varphi(n) = n\prod\limits_{p\mid n}\frac{p-1}{p}$ los rendimientos de la envolvente de
$$b(k) = k\prod_{p \leqslant k+1}\frac{p}{p-1} \sim k e^{\gamma} \log k.$$
Esta obligado salvajemente sobrestima el mayor $n$ al $k$ es grande, pero es razonable para bajita $k$ - tenemos $b(1) = 2$$b(2) = 6$, por lo que el obligado es fuerte por muy pequeño $k$. Para$k = 4$,$b(4) = 15$, mientras que la máxima $n$$12$, e $b(6) = \frac{105}{4}$, mientras que el mayor $n$$\varphi(n) \leqslant 6$$n = 14$, por lo que no es demasiado malo todavía. Incluso $b(680) \approx 7956$ no es totalmente absurdo.
Contamos con la condición adicional de que $\prod\limits_{p\mid n} (p-1) \leqslant k$, y que los límites de $n$ mucho más al $k$ no es pequeño. Para $k = 680$, la desigualdad de $k < 6!$ muestra que un $n$ $\varphi(n) \leqslant k$ puede tener en la mayoría de los cinco distintos primer divisores y que produce un salto de
$$n \leqslant 680 \cdot \frac{2}{1}\cdot \frac{3}{2} \cdot \frac{5}{4} \cdot \frac{7}{6}\cdot \frac{11}{10} = 3272.5$$
que ya está en el derecho de la bola del parque.
Para una útil obligado, a encontrar el mayor prime $q$$\prod\limits_{p \leqslant q} (p-1) \leqslant k$, y el conjunto de
$$c(k) = k\prod_{p \leqslant q} \frac{p}{p-1}.$$
Desde $q$ es de alrededor de $\log k$ al $k$ es grande, tenemos el comportamiento asintótico $c(k) \sim k e^{\gamma} \log \log k$.
Este - $c(k)$ - todavía sobreestimar (con la excepción de pequeñas $k$), pero no por mucho, el comportamiento asintótico es correcta.
Desde $\frac{p}{p-1}$ está disminuyendo, la relación $\frac{n}{\varphi(n)}$ es mayor al $n$ tiene muchos pequeños factores primos, de donde se espera que la máxima $n$ $\varphi(n)$ es casi un primorial - "casi un primorial" lo que significa que es un primorial multiplicado con pocos, si alguno, además de los números primos. Pero ya que además de la relación de $\frac{n}{\varphi(n)}$ también los valores de $\varphi(n)$ cerca de $k$ $n$ grande, es de esperar que, a menudo, multiplicando por un mayor prime al final se obtiene un mayor $n$ de los primos más pequeños aún no utilizados, y el uso de algunos pequeños primos más de una vez también puede traer a $\varphi(n)$ más cerca de la $k$ y por lo tanto conducen a un mayor $n$ de un squarefree número.
Sin embargo, no le puedo dar un algoritmo que no necesita de un poco de ensayo y error.
Si usted quiere encontrar el máximo de $n$ $\varphi(n) \leqslant k$ todos los $k$ que no exceda de un tamaño mediano enlazado $K$, el mejor método es, probablemente, para calcular los $\varphi(n)$ todos los $n \leqslant c(K)$ - una variación de la criba de Eratóstenes hace que la eficiente y, a continuación, analizar la matriz de destacar los valores más grandes con un determinado totient.
Para encontrar el mayor $n$ $\varphi(n) \leqslant k$ por una sola (grande) $k$, me gustaría empezar con el primorial $q\#$ donde $q$ es el más grande de la primera con la $\prod\limits_{p \leqslant q}(p-1) \leqslant k$, posiblemente sustituyendo $q$, con una mayor prime, y/o caída de $q$ y multiplicar con algunos pequeños primos para obtener el totient más cerca de $k$. De esta forma, no es demasiado malo límite inferior. Entonces, uno puede intentar algo más de reemplazos para buscar un mayor $n$, o si el intervalo entre el límite inferior y el límite superior es lo suficientemente pequeño, calcular el totients de los números entre los límites y buscar la mejor $n$.
Respecto a su comentario
A la inversa totient función de resolver el problema. ¿Cómo puedo obtener el mayor número de $n$ $\phi(n) = k$ para un determinado $k$?
Yo no soy demasiado optimista. Si se conoce el algoritmo para calcular el mayor $n$ $\varphi(n) = k$ eficiente, que probablemente funcionan bastante bien. A pesar de que uno tiene que comprobar varios candidatos totients $k$, uno es probable que pronto llegará uno de los que se obtiene el óptimo $n$, y luego de esperar que no quedan demasiados candidatos para comprobar. Pero yo no soy consciente de que un algoritmo eficiente. (Que no quiere decir mucho, sin embargo, ya que yo no soy un experto en el campo.)
