La inversión de la función totient

Question

Para qué valores de $n$ ¿la ecuación de $\phi(x) = n$ tiene al menos una solución? Es allí cualquier manera eficiente para comprobar un determinado $n$?

Es obvio que no tiene soluciones para los impares $n$. Y el más pequeño número para el que no tiene soluciones es $14$.

Answer 1

Ver http://oeis.org/A002202 y más referencias allí.

ACTUALIZACIÓN: Ver también mi reciente libro "cálculo de la (número o la suma de) los inversos de Euler totient y otros multiplicativo de funciones", que presenta un algoritmo genérico para encontrar la recíproca de una función multiplicativa para un determinado valor entero.

Answer 2

Recientemente he respondido a esta pregunta o duda acerca de la Carmichael función en las matemáticas.SE. El algoritmo utiliza un incondicional límite inferior por lo que debe funcionar igual de bien para las totient la función debido a la $\lambda(x) \le \phi(x)$. Mi respuesta (sólo uno) no ha sido aceptada y la pregunta tiene una recompensa que expira mañana. No quiero recibir una recompensa por defecto para una respuesta incorrecta, por lo que estoy publicando esto aquí ahora como una invitación para que me corrija en las matemáticas.SE. No es un algoritmo eficiente como este MO pregunta exige, pero me ofrecen porque ningún algoritmo aún no se ha dado respuesta.

También se relaciona Carmichael del totient función de la conjetura de que es que no existen soluciones únicas para esta ecuación.