¿Cuál es el valor mínimo de % que $n$ para cualquier $\phi(n) \ne \phi(k)$ $k<n,$donde $n=4m$?

Question

Deje $\phi(n)$ ser de Euler totient función. Para $n=4m$ ¿cuál es la menor $n$ para los que

$$\phi(n) \ne \phi(k) \textrm{ for any } k<n \textrm{ ?} \quad (1)$$

Al $n=4m+1$ $n>1$ el más pequeño es $n=5$ e al $n=4m+3$ $n=3.$ sin Embargo, cuando $n=4m+2$ la condición anterior, nunca puede ser satisfecho desde

$$\phi(4m+2) = (4m+2) \prod_{p | 4m+2} \left( 1 - \frac{1}{p} \right)$$ $$ = (2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = \phi(2m+1).$$

En el caso $n=4m,$ $n=2^{33}$ es un candidato y $\phi(2^{33})=2^{32}.$ Este valor satisface $(1)$ porque $\phi(n)$ es una potencia de $2$ precisamente al $n$ es el producto de una potencia de $2$ y cualquier número de los distintos números primos de Fermat:

$$2^1+1,2^2+1,2^4+1,2^8+1 \textrm{ and } 2^{16}+1.$$

Tenga en cuenta el $n=2^{32}$ no satisface la condición de $(1)$ debido a que el producto de los anteriores números primos de Fermat es $2^{32}-1$ $\phi(2^{32})=2^{31}=\phi(2^{32}-1)$ y $2^{32}-1 < 2^{32}.$

Las únicas soluciones a $\phi(n)=2^{32}$ son números de la forma $n=2^a \prod (2^{x_i}+1)$ donde $x_i \in \lbrace 1,2,4,8,16 \rbrace $ y $a+ \sum x_i = 33$ (tenga en cuenta que el producto puede estar vacío), así que todos estos números son necesariamente $ \ge 2^{33}.$

¿Por qué no muchos "pequeños" múltiplos de $4$ satisfacer la condición de $(1)$? Además, tenga en cuenta que para $n=2^a(2m+1)$ hemos

$$\phi(2^a(2m+1))= 2^a(2m+1) \prod_{p | 2^a(2m+1)} \left( 1 - \frac{1}{p} \right)$$ $$ = 2^{a-1}(2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = 2^{a-1}\phi(2m+1),$$

y así, por $a \ge 2,$ si $2^{a-1}\phi(2m+1)+1$ es el prime podemos tomar esto como nuestro valor de $k<n$ y tenemos $\phi(n)=\phi(k).$ Esto, junto con la existencia de los números primos de Fermat, parece ser ¿por qué es difícil para satisfacer al $n=4m.$

Sólo he hecho cálculos de la mano hasta ahora, así que no sería sorpresa si la respuesta es mucho más pequeño que mi sugerencia. El problema está dentro de la alcance de un equipo, y, posiblemente, más análisis sin la ayuda de un ordenador. Pero, de todos modos, me he decidido a preguntar aquí como muchos de ustedes tienen fácil acceso a buenos matemáticos software y estoy muy intrigado en saber si hay una solución más pequeña que $2^{33}.$

Algunos antecedentes:

Esta pregunta surgió en mi búsqueda para acotar la función de $\Phi(n)$ define de la siguiente manera.

Deje $\Phi(n)$ el número de valores distintos que adoptado por $\phi(k)$ $1 \le k \le n.$ Por ejemplo, $\Phi(13)=6$ desde $\phi(k)$ toma los valores $\lbrace 1,2,4,6,10,12 \rbrace$ $1 \le k \le 13.$

Está claro que $\Phi(n)$ aumenta y aumenta por $1$ en cada primer valor de $n,$ con la excepción de $n=2,$ pero aumenta también en otros valores. Por ejemplo, $\Phi(14)=6$ $\Phi(15)=7.$

En la actualidad, por un límite superior, tengo la esperanza de hacerlo mejor que $\Phi(n) \le \lfloor (n+1)/2 \rfloor .$

Pero este no es el problema en el momento, aunque bien puede convertirse en una cuestión separada.

Este trabajo se origina a partir de esta stackexchange problema.

Answer 1

La respuesta es

\[33817088 = 2 ^ 9 \cdot 257 ^ 2 = 2 ^ 9 \cdot (2 ^ 8 + 1) ^ 2\]

con

\[\phi(33817088) = 16842752 = 2 ^ {16} \cdot (2 ^ 8 + 1) = 2 ^ {16} \cdot 257\;. \]

Aquí está el código Java se encuentra (tarda unos segundos en un MacBook Pro):

import java.util.Arrays;

public class Totient {
    final static int mod4 = 0;     // remainder mod 4 to test                                                                                                                                                                                                                      
    final static int n = 40000000; // highest number to test                                                                                                                                                                                                                       

    static boolean [] prime = new boolean [n / 2]; // prime [i] : is 2i + 1 prime?                                                                                                                                                                                                 
    static boolean [] seen = new boolean [n];      // seen [i] : we've seen phi (n) = i                                                                                                                                                                                            
    static int [] phi = new int [n];               // phi [i] : phi (i)                                                                                                                                                                                                            

    public static void main (String [] args) {
        Arrays.fill (prime,true);
        Arrays.fill (seen,false);
        Arrays.fill (phi,1);

        // calculate the primes we need                                                                                                                                                                                                                                            
        int limit = (int) Math.sqrt (n); // highest factor to test                                                                                                                                                                                                                 
        for (int p = 3;p <= limit;p += 2) // loop over odd integers                                                                                                                                                                                                                
            if (prime [p >> 1])            // only test primes p                                                                                                                                                                                                                   
                for (int k = 3*p;k < n;k += 2*p) // loop over odd multiples of p                                                                                                                                                                                                   
                    prime [k >> 1] = false;      // sieve them out                                                                                                                                                                                                                 

        // fill phi by looping over all primes                                                                                                                                                                                                                                     
        fill (2);
        for (int p = 3;p < n;p += 2)
            if (prime [p >> 1])
                fill (p);

        // now go through phi, remembering which values we've already seen                                                                                                                                                                                                         
        for (int i = 1;i < n;i++) {
            if ((i & 3) == mod4 && !seen [phi [i]]) {
                System.out.println ("found " + i + " with phi (" + i + ") = " + phi [i]);
                return;
            }
            seen [phi [i]] = true;
        }
    }

    // multiply all phi values by their factors of prime p                                                                                                                                                                                                                         
    static void fill (int p) {
        // once for the first factor of p                                                                                                                                                                                                                                          
        for (int i = p;i < n;i += p)
            phi [i] *= p - 1;

        // and then for the remaining factors                                                                                                                                                                                                                                      
        long pow = p * (long) p; // long to avoid 32-bit overflow                                                                                                                                                                                                                  
        while (pow < n) {
            for (int i = (int) pow;i < n;i += pow)
                phi [i] *= p;
            pow *= p;
        }
    }
}