Números intocables ^α

Un número intocable es un número entero positivo que no puede expresarse como la suma de todos los divisores propios de cualquier número entero positivo (incluido el número intocable en sí).

Por ejemplo, el número 4 no es intocable ya que es igual a la suma de los divisores propios de 9: 1 + 3 = 4. El número 5 es intocable ya que no es la suma de los divisores propios de ningún entero positivo. 5 = 1 + 4 es la única forma de escribir 5 como la suma de enteros positivos distintos, incluido 1, pero si 4 divide un número, 2 también lo hace, por lo que 1 + 4 no puede ser la suma de todos los divisores propios de cualquier número (ya que la lista de factores debería contener 4 y 2).

Se cree que el número 5 es el único número intocable impar, pero esto no se ha demostrado: se derivaría de una versión ligeramente más fuerte de la conjetura de Goldbach. ^β

Hay infinitos números intocables, un hecho que fue comprobado por Paul Erdős.

Algunas propiedades de los intocables:

• No intocable es 1 mayor que un primo
• No intocable es 3 mayor que un primo, excepto 5
• No intocable es un número perfecto
• Hasta ahora, todos los intocables aparte de 2 y 5 son compuestos.

Objetivo

Cree un programa o función que tome un número natural a ntravés de parámetros de entrada o función estándar e imprima los primeros nnúmeros intocables.

La salida debe tener una separación entre los números, pero esto puede ser cualquier cosa (es decir, líneas nuevas, comas, espacios, etc.).

Esto debería poder funcionar al menos 1 <= n <= 8153. Esto se basa en el hecho de que el archivo b proporcionado para la entrada OEIS ^γ sube a n = 8153.

Las lagunas estándar no están permitidas, como de costumbre.

Ejemplo de E / S

1    -> 2
2    -> 2, 5
4    -> 2, 5, 52, 88
10   -> 2, 5, 52, 88, 96, 120, 124, 146, 162, 188
8153 -> 2, 5, 52, 88, 96, 120, ..., ..., ..., 59996

Este es el código de golf , por lo que gana el menor número de bytes.

^{α - Wikipedia , β - MathWorld , γ - OEIS}

^{Por alguna razón, esto se marcó como un duplicado de la pregunta 'encontrar números semiperfectos', sin embargo, las tareas son completamente diferentes. En este caso, debe verificar para asegurarse de que ninguna suma de divisores perfectos de ningún número natural pueda igualar un cierto número.}

Pyth, 21 bytes

.f!fqZsf!%TYStTSh^Z2Q

Advertencia: increíblemente lento. Prueba de funcionamiento y sincronización a continuación.

$ time pyth -c '.f!fqZsf!%TYStTSh^Z2Q' <<< 3
[2, 5, 52]

real    2m46.463s
user    2m46.579s
sys 0m0.004s

Básicamente es la fuerza bruta posible, pone a prueba las factorizaciones hasta el posible número solitario al cuadrado más uno.

C, 104 bytes

j,i,z,w;u(y){for(z=2;y;z++)for(w=0;(++w<z*z||0&printf("%i ",z)+y--)&&j^z;)for(i=j=0;++i<w;j+=i*!(w%i));}

Tomará unos minutos para y > 20, pero lo que sea.

Java, 310 bytes

class U{int[] p;U(int e){p=new int[(int)4e9];for(int i=1,c=0;c<e;i++)if(u(i)>0){System.out.println(i);c++;}}int p(int n){if(p[n]!=0)return p[n];int i,s=1;for(i=2;i<=n-1;i++)s+=n%i==0?i+(n/i!=i?n/i:0):0;return(p[n]=s);}int u(int n){if(n==1)return 0;for(int i=2;i<=(n-1)*(n-1);i++)if(p(i)==n)return 0;return 1;}}

Jugué lo mejor que pude, pero estaba más interesado en asegurarme de que funcionara en un tiempo razonable. La versión sin pelar es probablemente más interesante.

public class Untouchable {
    int[] properDivisorSumMap;


    public Untouchable(int estimatedMaxium){
        properDivisorSumMap = new int[(estimatedMaxium-1)*(estimatedMaxium-1)];
    }


    public int properDivisorSum(int n){
        if(properDivisorSumMap[n] != 0){
            return properDivisorSumMap[n];
        }

        int sum = 1;
        for(int i=2;i<=(int)Math.sqrt(n);i++){
            if(n%i==0){
                sum+=i;
                if(n/i != i){
                    sum+=n/i;
                }
            }
        }
        properDivisorSumMap[n] = sum;
        return sum;
    }


    public boolean untouchable(int n){
        if(n==1){
            return false;
        }
        for(int i=2;i<=(n-1)*(n-1);i++){
            if(properDivisorSum(i) == n){
                return false;
            }
        } 
        return true;
    }


    public static void main(String[] args){
        Untouchable test = new Untouchable(8480);

        int elements = Integer.parseInt(args[0]);

        for(int i=1,count=0;count < elements;i++){
            if(test.untouchable(i)){
                System.out.printf("%4d: %4d%n",count,i);
                count++;
            }
        }
    }
}

Go, 396 bytes

Realmente no es golf, pero puede hacer todo el rango requerido. Se ejecuta en aproximadamente ~ 20 minutos y necesita ~ 7 GB (independiente de n). Hace una matriz gigante para calcular la suma de divisores para todos los números hasta 59997 al cuadrado.

func untouchable(n int) {
    const C = 59997
    const N = C * C
    s := make([]uint16, N)
    for d := 1; d < N; d++ {
        for i := 2 * d; i < N; i += d {
            v := int(s[i]) + d
            if v > C {
                v = C + 1 // saturate at C+1
            }
            s[i] = uint16(v)
        }
    }
    var m [C]bool
    for i := 2; i < N; i++ {
        if s[i] < C {
            m[s[i]] = true
        }
    }
    for i := 2; n > 0; i++ {
        if !m[i] {
            println(i)
            n--
        }
    }
}