Bei einer nicht negativen Ganzzahl Nwird die kleinste ungerade positive Ganzzahl ausgegeben, die eine starke Pseudoprime für alle ersten NPrimzahlen darstellt.

Dies ist die OEIS-Sequenz A014233 .

Testfälle (einseitig indiziert)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Testfälle für N > 13sind nicht verfügbar, da diese Werte noch nicht gefunden wurden. Wenn Sie den / die nächsten Begriff (e) in der Sequenz finden, senden Sie ihn / sie unbedingt an OEIS!

Regeln

• Sie können wählen, ob Sie Neinen Null- oder einen Ein-Index-Wert verwenden möchten.
• Es ist akzeptabel, dass Ihre Lösung nur für die Werte funktioniert, die im ganzzahligen Bereich Ihrer Sprache darstellbar sind (also bis zu N = 1264-Bit-Ganzzahlen ohne Vorzeichen), aber Ihre Lösung muss theoretisch für jede Eingabe funktionieren, mit der Annahme, dass Ihre Sprache Ganzzahlen beliebiger Länge unterstützt.

Hintergrund

Jede positive gerade ganze Zahl xkann in der Form geschrieben werden , x = d*2^swo dungerade ist. dund skann durch wiederholtes Dividieren berechnet werden , num 2 , bis der Quotient nicht mehr durch 2 teilbar dist , dass Endquotienten, und sist die Anzahl von Malen 2 dividieren n.

Wenn eine positive ganze Zahl neine Primzahl ist, lautet der kleine Satz von Fermat :

In jedem endlichen Feld Z/pZ (wo peine Primzahl ist) 1sind 1und -1(oder äquivalent 1und p-1) die einzigen Quadratwurzeln von .

Wir können diese drei Tatsachen verwenden, um zu beweisen, dass eine der folgenden beiden Aussagen für eine Primzahl wahr sein muss n(wo d*2^s = n-1und rin welcher Zahl eine ganze Zahl ist [0, s)):

Der Miller-Rabin-Primalitätstest testet das Gegenteil der obigen Behauptung: Wenn es eine Basis gibt a, bei der beide oben genannten Bedingungen falsch sind, nist dies keine Primzahl. Diese Basis awird als Zeuge bezeichnet .

Jetzt [1, n)wäre das Testen jeder Basis in unerschwinglicher Rechenzeit für große Unternehmen n. Es gibt eine probabilistische Variante des Miller-Rabin-Tests, die nur einige zufällig ausgewählte Basen im endlichen Feld testet. Es wurde jedoch herausgefunden, dass das Testen nur von primären aBasen ausreichend ist, und daher kann der Test auf effiziente und deterministische Weise durchgeführt werden. Tatsächlich müssen nicht alle Primzahlenbasen getestet werden - es ist nur eine bestimmte Anzahl erforderlich, und diese Anzahl hängt von der Größe des Werts ab, dessen Primalität getestet wird.

Wenn nicht genügend Primzahlenbasen getestet werden, kann der Test falsch positive Ergebnisse liefern - ungerade zusammengesetzte ganze Zahlen, bei denen der Test ihre Zusammensetzung nicht nachweist. Insbesondere, wenn eine Basis adie Zusammensetzung einer ungeraden zusammengesetzten Zahl nicht beweisen kann, wird diese Zahl als starkes Pseudoprime zur Basis bezeichnet a. Bei dieser Herausforderung geht es darum, die ungeraden zusammengesetzten Zahlen zu finden, die starke Pseudoprimes für alle Basen sind, die kleiner oder gleich der dritten NPrimzahl sind (was gleichbedeutend damit ist, dass sie starke Pseudoprimes für alle Primzahlen sind, die kleiner oder gleich der Ndritten Primzahl sind). .

C 349 295 277 267 255 Bytes

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Nimmt 1-basierte Eingabe für stdin auf, zB:

echo "1" | ./millerRabin

Es wird sicherlich nicht in naher Zukunft neue Werte in der Sequenz entdecken, aber es wird die Arbeit erledigen. UPDATE: jetzt noch langsamer!

• Etwas schneller und kürzer, inspiriert von Neil A's Antwort ( a^(d*2^r) == (a^d)^(2^r))
• Erheblich langsamer, nachdem erkannt wurde, dass alle Lösungen für diese Herausforderung ungerade sind, sodass nicht explizit erzwungen werden muss, dass nur ungerade Zahlen überprüft werden.
• Jetzt mit GCCs __int128, die kürzer sind als unsigned long longbei der Arbeit mit größeren Nummern! Auch auf Little-Endian-Rechnern %llufunktioniert der printf mit noch einwandfrei.

Weniger reduziert

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

(Veraltete) Aufschlüsselung

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Wie bereits erwähnt, wird hier eine 1-basierte Eingabe verwendet. Für n = 0 ergibt sich jedoch eine 9, die der verwandten Sequenz https://oeis.org/A006945 folgt . Nicht länger; jetzt hängt es an 0.

Sollte für alle n funktionieren (zumindest bis die Ausgabe 2 ^ 64 erreicht), ist aber unglaublich langsam. Ich habe es auf n = 0, n = 1 und (nach langem Warten) auf n = 2 überprüft .

Python 2, 633 465 435 292 282 275 256 247 Bytes

0-indiziert

Stellen Sie Ihre Implementierung in Frage und probieren Sie etwas Neues aus

Das Konvertieren von einer Funktion in ein Programm spart irgendwie einige Bytes ...

Wenn mir Python 2 eine kürzere Möglichkeit bietet, das Gleiche zu tun, verwende ich Python 2. Division ist standardmäßig eine Ganzzahl, also eine einfachere Möglichkeit, durch 2 zu teilen, und printbenötigt keine Klammern.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Probieren Sie es online!

Python ist im Vergleich zu anderen Sprachen notorisch langsam.

Definiert einen Testteilungs-Test auf absolute Korrektheit und wendet dann wiederholt den Miller-Rabin-Test an, bis ein Pseudoprim gefunden wird.

Probieren Sie es online!

EDIT : Endlich golfen die Antwort

EDIT : Wird minfür den Primalitätstest der Testabteilung verwendet und in a geändert lambda. Weniger effizient, aber kürzer. Konnte mir auch nicht helfen und benutzte ein paar bitweise Operatoren (kein Längenunterschied). Theoretisch sollte es (etwas) schneller gehen.

EDIT : Danke @ Dave. Mein Redakteur hat mich beschimpft. Ich dachte, ich benutze Tabulatoren, aber es wurde stattdessen in 4 Leerzeichen umgewandelt. Ging auch so ziemlich jeden einzelnen Python-Tipp durch und wendete ihn an.

BEARBEITEN : Umgestellt auf 0-Indizierung, ermöglicht es mir, ein paar Bytes beim Generieren der Primzahlen zu sparen. Auch ein paar Vergleiche überdacht

EDIT : Verwendet eine Variable, um das Ergebnis der Tests anstelle von for/elseAnweisungen zu speichern .

BEARBEITEN : Verschob das lambdaInnere der Funktion, um die Notwendigkeit eines Parameters zu beseitigen.

BEARBEITEN : In ein Programm konvertiert, um Bytes zu sparen

EDIT : Python 2 spart mir Bytes! Außerdem muss ich die Eingabe nicht in konvertierenint

Perl + Math :: Prime :: Util, 81 + 27 = 108 Bytes

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Laufen Sie mit -lpMMath::Prime::Util=:all(27-Byte-Strafe, autsch).

Erläuterung

Es ist nicht nur Mathematica, das für praktisch alles eine eingebaute Funktion hat. Perl verfügt über CPAN, eines der ersten großen Bibliotheksrepositorys, und eine riesige Sammlung vorgefertigter Lösungen für Aufgaben wie diese. Leider werden sie nicht standardmäßig importiert (oder sogar installiert), was bedeutet, dass es grundsätzlich nie eine gute Option ist, sie in Code-Golf zu verwenden , aber wenn eine davon genau zum Problem passt ...

Wir durchlaufen aufeinanderfolgende ganze Zahlen, bis wir eine finden, die keine Primzahl und dennoch eine starke Pseudoprime für alle ganzzahligen Basen von 2 bis zur n- ten Primzahl ist. Die Befehlszeilenoption importiert die Bibliothek, die das betreffende eingebaute Element enthält, und legt auch die implizite Eingabe fest (auf Zeile für Zeile; Math::Prime::Utilverfügt über eine eigene eingebaute Bignum-Bibliothek, die keine Zeilenumbrüche in den Ganzzahlen mag). Hierbei wird der Perl-Standardtrick $\(Ausgabezeilentrennzeichen) als Variable verwendet, um umständliche Parser zu reduzieren und die implizite Generierung der Ausgabe zu ermöglichen.

Beachten Sie, dass wir hier verwenden müssen, um is_provable_primeeher einen deterministischen als einen probabilistischen Primetest anzufordern. (Vor allem, da ein probabilistischer Primetest wahrscheinlich in erster Linie mit Miller-Rabin durchgeführt wird, und wir in diesem Fall keine verlässlichen Ergebnisse erwarten können!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 Bytes, in Zusammenarbeit mit @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Laufen Sie mit -lpMntheory=:all(17-Byte-Strafe).

Dies verwendet ein paar Perl-Golftricks, die ich entweder nicht kannte (anscheinend hat Math :: Prime :: Util eine Abkürzung!), Die ich kannte, aber nicht zu verwenden dachte ( }{um $\implizit einmal statt "$_$\"implizit jeder Zeile auszugeben ). , oder wussten über, aber irgendwie geschafft, falsch anzuwenden (Klammern aus Funktionsaufrufen entfernen). Vielen Dank an @Dada für diesen Hinweis. Abgesehen davon ist es identisch.