Nombres intouchables ^α

Un nombre intouchable est un entier positif qui ne peut pas être exprimé comme la somme de tous les diviseurs propres d'un entier positif (y compris le nombre intouchable lui-même).

Par exemple, le nombre 4 n'est pas intouchable car il est égal à la somme des diviseurs propres de 9: 1 + 3 = 4. Le nombre 5 est intouchable car il n'est pas la somme des diviseurs appropriés d'un quelconque entier positif. 5 = 1 + 4 est le seul moyen d'écrire 5 comme la somme d'entiers positifs distincts, y compris 1, mais si 4 divise un nombre, 2 le fait aussi, donc 1 + 4 ne peut pas être la somme de tous les diviseurs propres d'un nombre (puisque la liste des facteurs devrait contenir à la fois 4 et 2).

Le nombre 5 serait le seul nombre impair intouchable, mais cela n'a pas été prouvé: il découlerait d'une version légèrement plus forte de la conjecture de Goldbach. ^β

Il existe une infinité de nombres intouchables, un fait qui a été prouvé par Paul Erdős.

Quelques propriétés d'intouchables:

• Aucun intouchable n'est supérieur à un nombre premier
• Aucun intouchable est 3 supérieur à un nombre premier, sauf 5
• Aucun intouchable n'est un nombre parfait
• Jusqu'à présent, tous les intouchables à l'exception de 2 et 5 sont composites.

Objectif

Créez un programme ou une fonction qui prend un nombre naturel nvia des paramètres d'entrée ou de fonction standard et imprime les premiers nnombres intouchables.

La sortie doit avoir une séparation entre les nombres, mais cela peut être n'importe quoi (par exemple, sauts de ligne, virgules, espaces, etc.).

Cela devrait pouvoir fonctionner au moins 1 <= n <= 8153. Ceci est basé sur le fait que le fichier b fourni pour l'entrée OEIS ^γ monte n = 8153.

Les failles standard sont interdites, comme d'habitude.

Exemple d'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

Il s'agit de code-golf , donc le moins d'octets gagne.

^{α - Wikipédia , β - MathWorld , γ - OEIS}

^{Pour une raison quelconque, cela a été marqué comme un double de la question «trouver des nombres semi-parfaits», mais les tâches sont complètement différentes. Dans ce cas, vous devez vous assurer qu'aucune somme de diviseurs parfaits d'un nombre naturel ne peut égaler un certain nombre.}

Pyth, 21 octets

.f!fqZsf!%TYStTSh^Z2Q

Avertissement: incroyablement lent. Test de fonctionnement et calendrier ci-dessous.

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

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

C'est fondamentalement aussi brutal que possible, teste les factorisations jusqu'au nombre de solitaires potentiels au carré plus un.

C, 104 octets

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));}

Cela prendra quelques minutes pour y > 20, mais peu importe.

Java, 310 octets

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;}}

J'ai joué du golf aussi bien que possible, mais j'étais plus intéressé à m'assurer qu'il se déroulait dans un délai raisonnable. La version non vitrée est probablement plus intéressante

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 octets

Pas vraiment joué au golf, mais il peut faire toute la gamme requise. Fonctionne en environ 20 minutes et nécessite environ 7 Go (indépendamment de n). Donne un tableau géant pour calculer la somme des diviseurs pour tous les nombres jusqu'à 59997 au carré.

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--
        }
    }
}