Bertrands Postulat besagt, dass es für jede ganze Zahl n ≥ 1 mindestens eine Primzahl p gibt, so dass n <p ≤ 2n ist . Um diesen Satz für n <4000 zu verifizieren, müssen wir nicht 4000 Fälle prüfen: Der Landau-Trick besagt, dass es ausreicht, dies zu prüfen
2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 5003
sind alle prime. Da jede dieser Zahlen kleiner als das Doppelte ihrer Vorgängerzahl ist, enthält jedes Intervall {y: n <y ≤ 2n} mindestens eine dieser Primzahlen.
Diese Folge von Zahlen sind die Bertrand-Primzahlen (OEIS A006992) und sie sind wie folgt definiert:
a(1) = 2
a(n) = largest prime below 2a(n-1)
Herausforderung
Implementieren Sie diese Sequenz. Du darfst schreiben
- eine Funktion oder ein Programm, die / das mit einigen n ein (n) (0 oder 1 indiziert) zurückgibt ,
- eine Funktion oder ein Programm, die / das mit einigen n die ersten n (oder n-1 oder n + 1 ) Einträge dieser Sequenz zurückgibt ,
- Eine unendliche Liste oder ein Stream oder Generator oder ein ähnliches Äquivalent in Ihrer Sprache.
Fx.ØØ
ist so nah ... Funktioniert für alles obenn > 2
.$F·ÅPθ
für die gleiche Bytezahl.Haskell , 50 Bytes
Probieren Sie es online!
Gibt eine unendliche Liste aus.
Haskell , 40 Bytes?
Probieren Sie es online!
Dies funktioniert, wenn Bertrands Primzahlen für 2 keine Fermat-Pseudoprimes enthalten .
quelle
Gelee , 6 Bytes
Probieren Sie es online!
0-indiziert.
Erläuterung
quelle
MATL , 9 Bytes
Eingänge n , Ausgänge a ( n ), 1-indiziert.
Probieren Sie es online!
Erläuterung
quelle
Stax , 10 Bytes
Führen Sie Testfälle aus
Dieses Problem hat einen Fehler in der Implementierung von stax aufgedeckt
:p
, bei dem es sich um eine Anweisung handelt, bei der die höchste Primzahl unter der Eingabe liegt. Wenn es richtig funktioniert, gibt es eine56-Byte-Lösung.Aber leider nicht, und es gibt nicht.Als Schöpfer der Sprache werde ich das Problem beheben, aber es scheint billig zu sein, es zu beheben und zu verwenden, nachdem das Problem veröffentlicht wurde.Wie auch immer, hier ist die entsprechende ASCII-Darstellung des obigen Programms.
Die Umsetzung der Problemstellung ist relativ unkompliziert. Das einzig interessante daran ist die Verwendung der
gs
Generatorform. Generatoren sind eine Konstruktionsfamilie, die eine Anfangsbedingung, eine Transformation und einen Filter kombiniert, um einen oder mehrere zufriedenstellende Werte zu erzeugen. In diesem Fall wird es anstelle der fehlerhaften:p
Anweisung verwendet.Bearbeiten: Hier ist die 6-Byte-Lösung, für die jedoch ein Bugfix erforderlich ist, der erst nach dem Posten dieser Herausforderung angewendet wurde.
quelle
Python 2 , 63 Bytes
Probieren Sie es online!
Druckt für immer.
Verwendet den Wilson-Theorem-Primgenerator, obwohl das Generieren von Primzahlen für dieses Problem umständlich ist. Verfolgt die aktuell größte gesehene Primzahl
r
und die Verdopplungsgrenzem
.Dabei werden
P*=k
nichtP*=k*k
wie üblich zwei Bytes gespeichert , da der einzige Effekt darin besteht, zu behaupten, dass 4 eine Primzahl ist, und die Folge der Verdopplung diese verfehlt.quelle
CJam (15 Bytes)
Online-Demo . Beachten Sie, dass dies 0-indiziert ist.
Ein effizienterer Ansatz wäre, rückwärts zu suchen. Dies erfordert jedoch ein Zeichen mehr, da implicit
,
(range) nicht verwendet werden kann :quelle
Japt ,
16141312 BytesZwei Lösungen zum Preis von einer, beide 1-indiziert.
N-ter Begriff
Endlich eine Herausforderung, für die ich eine funktionierende Lösung schreiben kann
F.g()
.Versuch es
Erste N Begriffe
Versuch es
quelle
Pari / GP , 34 Bytes
Probieren Sie es online!
quelle
Python 2 , 64 Bytes
Probieren Sie es online! Druckt die Sequenz auf unbestimmte Zeit
quelle
Haskell , 58 Bytes
Probieren Sie es online!
quelle
Python 2 , 68 Bytes
Druckt die Sequenz auf unbestimmte Zeit (Sie müssen das zweite Mal auf "Ausführen" klicken, um die Ausführung zu stoppen).
Probieren Sie es online!
Python 3 , 90 Bytes
Gibt den n- ten Term zurück.
Probieren Sie es online!
quelle
C (GCC) ,
9787868079 BytesP
in die Hauptschleife eingefügt haben.printf
Anrufs wurde .i
-ten Sequenzeintrag (0-indiziert) zurückgegeben haben, anstatt einen nie endenden Stream auszugeben.Probieren Sie es online!
quelle
Attache , 38 Bytes
Probieren Sie es online!
0-basiert; gibt das zurück
n
th Bertrand prime zurück.Es gibt derzeit kein eingebautes Element, um die vorherigen / nächsten Primzahlen zu finden, daher verwende ich das
Series
eingebaute Element, um alle Primzahlen bis zu zu berechnen2*$[_-1]
. Dieser letzte Ausdruck verwendet implizite Rekursion (gebunden an$
), um die Wiederholungsrelation einfach zu definieren. Die if-Bedingung wird verwendet, um eine Grundbedingung zu bestimmen.quelle
Perl 6 , 35 Bytes
Probieren Sie es online!
Dieser Ausdruck ist eine unendliche Liste von Bertrand-Primzahlen.
quelle
Netzhaut , 39 Bytes
Probieren Sie es online! Erläuterung:
Beginnen Sie mit 1.
Wiederholen Sie die Schleife mit dem Eingang als Schleifenzahl.
Verdoppeln Sie den Wert.
Finde die höchste Primzahl, die kleiner als der Wert ist.
Drucke es aus.
quelle
Ruby , 51 + 7 (-rprime) = 58 Bytes
Probieren Sie es online!
Eine Lamba,
n
die dienth
Bertrand-Primzahl mit dem Index 0 annimmt und zurückgibt . Hier ist nicht viel, aber lass es mich trotzdem loswerden:Ruby , 48 + 7 = 55 Bytes
Probieren Sie es online!
Zum Spaß gibt es hier eine Endloslösung. Es druckt wie es geht und erfordert einen Interrupt. Abhängig davon, wann genau Sie unterbrechen, wird die Ausgabe möglicherweise angezeigt oder nicht. Ungolfed:
quelle
APL (Dyalog Extended) , 12 Byte
Nimmt Eingaben vom Benutzer als N und gibt das N-te Element der Sequenz zurück (0-indiziert).
Probieren Sie es online!
Erläuterung:
quelle
R 87 Bytes
Gegebene
n
Leistungena(n)
Probieren Sie es online!
Ich arbeite noch an "Gegeben n Ausgabe a (1), a (2) ... a (n)". Ich dachte, ich könnte diesen Code nur geringfügig ändern, aber es scheint schwieriger zu sein.
quelle