Die Unberührbaren

9

Unberührbare Zahlen α

Eine unberührbare Zahl ist eine positive ganze Zahl, die nicht als Summe aller richtigen Teiler einer positiven ganzen Zahl (einschließlich der unberührbaren Zahl selbst) ausgedrückt werden kann.

Zum Beispiel ist die Zahl 4 nicht unantastbar, da sie gleich der Summe der richtigen Teiler von 9: 1 + 3 = 4 ist. Die Zahl 5 ist unantastbar, da sie nicht die Summe der richtigen Teiler einer positiven ganzen Zahl ist. 5 = 1 + 4 ist die einzige Möglichkeit, 5 als Summe verschiedener positiver Ganzzahlen einschließlich 1 zu schreiben. Wenn 4 jedoch eine Zahl teilt, gilt dies auch für 2, sodass 1 + 4 nicht die Summe aller richtigen Teiler einer Zahl sein kann (seit Die Liste der Faktoren müsste sowohl 4 als auch 2 enthalten.

Es wird angenommen, dass die Zahl 5 die einzige unberührbare Zahl ist, aber dies wurde nicht bewiesen: Sie würde sich aus einer etwas stärkeren Version der Goldbach-Vermutung ergeben. β

Es gibt unendlich viele unantastbare Zahlen, eine Tatsache, die Paul Erdős bewiesen hat.

Einige Eigenschaften von Unberührbaren:

  • Kein Unberührbarer ist 1 größer als eine Primzahl
  • Kein Unberührbarer ist 3 größer als eine Primzahl, außer 5
  • Kein Unberührbarer ist eine perfekte Zahl
  • Bisher sind alle Unberührbaren außer 2 und 5 zusammengesetzt.

Zielsetzung

Erstellen Sie ein Programm oder eine Funktion , die eine natürliche Zahl nüber Standardeingabe- oder Funktionsparameter verwendet und die ersten nunberührbaren Zahlen druckt .

Die Ausgabe muss zwischen den Zahlen getrennt sein, dies kann jedoch alles sein (z. B. Zeilenumbrüche, Kommas, Leerzeichen usw.).

Dies sollte zumindest funktionieren können 1 <= n <= 8153. Dies basiert auf der Tatsache, dass die für den OEIS-Eintrag γ bereitgestellte b-Datei bis zu reicht n = 8153.

Standardschlupflöcher sind wie üblich nicht zulässig.

Beispiel E / A.

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

Dies ist , also gewinnt die geringste Anzahl von Bytes.


α - Wikipedia , β - MathWorld , γ - OEIS


Aus irgendeinem Grund wurde dies als Duplikat der Frage "Semiperfect Numbers finden" markiert, die Aufgaben sind jedoch völlig unterschiedlich. In diesem Fall müssen Sie überprüfen, ob keine Summe perfekter Teiler einer natürlichen Zahl einer bestimmten Zahl entsprechen kann.

Kade
quelle
Dies ist rein spekulativ, da ich noch nicht wirklich darüber nachgedacht habe, wie ich das lösen würde: Wäre es Betrug, wenn ich eine Obergrenze für die resultierenden Zahlen annehmen würde? Sagen Sie, wenn ich Code geschrieben habe, der nur unberührbare Zahlen bis zu 60.000 findet? Das würde ausreichen, um den Eingangsbereich abzudecken. Aber das weiß ich natürlich nur aufgrund der von Ihnen angegebenen Teilergebnisse.
Reto Koradi
Ich denke es wäre okay. Es ist technisch nicht hartcodiert die Ergebnisse, verletzt nicht Standardlücken, soweit ich weiß. Solange es zum Rest der Spezifikation passt, ist das in Ordnung.
Kade
@vihan Auf keinen Fall.
Kade

Antworten:

6

Pyth, 21 Bytes

.f!fqZsf!%TYStTSh^Z2Q

Warnung: Unglaublich langsam. Testlauf und Timing unten.

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

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

Es ist im Grunde genommen so brutal wie möglich und testet Faktorisierungen bis zur potenziellen einsamen Zahl im Quadrat plus eins.

isaacg
quelle
4

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

Es wird ein paar Minuten dauern für y > 20, aber was auch immer.

Oberon
quelle
2

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

Ich habe so gut ich konnte Golf gespielt, aber ich war mehr daran interessiert sicherzustellen, dass es in angemessener Zeit lief. Die unglofed Version ist wahrscheinlich interessanter

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++;
            }
        }
    }
}
Ankh-Morpork
quelle
1

Los, 396 Bytes

Nicht wirklich Golf gespielt, aber es kann die gesamte erforderliche Reichweite erreichen. Läuft in ca. 20 Minuten und benötigt ca. 7 GB (unabhängig von n). Erstellt ein riesiges Array, um die Summe der Teiler für alle Zahlen bis zu 59997 im Quadrat zu berechnen.

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--
        }
    }
}
Keith Randall
quelle