Bertrands Primes

24

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.
Fehler
quelle

Antworten:

8

Oktave , 32 Bytes

k=2
do k=primes(k+k)(end)until 0

Druckt die Werte auf unbestimmte Zeit weiter (vor jedem Wert steht k =).

Probieren Sie es online!


Oktave , 42 Bytes

k=2
for i=2:input('')k=primes(k+k)(end)end

Nimmt n als Eingabe und gibt die n ersten Werte aus (vor jedem Wert steht k =).

Probieren Sie es online!


Oktave , 51 Bytes

k=2;for i=2:input('')k=primes(k+k)(end);end
disp(k)

Ähnlich wie Luis Mendos MATL-Antwort . Nimmt n als Eingabe und gibt a (n) aus (1-indiziert).

Probieren Sie es online!


Oktave , 60 Bytes

k=2;for i=2:input('')k*=2;while~isprime(--k)
end
end
disp(k)

Nimmt n als Eingabe und gibt a (n) aus (1-indiziert).

Probieren Sie es online!

Steadybox
quelle
7

J , 11 Bytes

_4&(p:+:)2:

Probieren Sie es online!

0-indiziert.

_4&(p:+:)2:  Input: integer n
         2:  Constant 2
_4&(    )    Repeat n times
      +:       Double
_4  p:         Find the largest prime less than the double
Meilen
quelle
6

05AB1E , 14 7 6 Bytes

$F·.ØØ

Probieren Sie es online!


1-indizierte Antwort (es sei denn, 0 soll 1 ausgeben), Erklärung:

$       # Push 1 and input (n)...
 F      # n-times do... 
  ·     # Double the current prime (first iteration is 1*2=2).
   .ØØ  # Find prime slightly less than double the current prime.

Es ist 1-indiziert, weil alle Iterationen eine 'Dummy'-Iteration mit haben n=1.

Magische Kraken-Urne
quelle
Fx.ØØist so nah ... Funktioniert für alles oben n > 2.
Magic Octopus Urn
1
Ich hatte $F·ÅPθfür die gleiche Bytezahl.
Emigna
@Emigna hatte? Das ist wie 0% das gleiche haha. Ich meine, technisch das gleiche, aber nicht. Konnte es noch posten; P.
Magic Octopus Urn
5

Gelee , 6 Bytes

2ḤÆp$¡

Probieren Sie es online!

0-indiziert.

Erläuterung

2ḤÆp$¡  Main link. Input: n
2       Constant 2
    $¡  Repeat n times
 Ḥ        Double
  Æp      Find the largest prime less than the double
Meilen
quelle
Poke, du brauchst jetzt ein anderes Byte ;) ...
Magic Octopus Urn
@MagicOctopusUrn Eine Eingabe von 0 gibt 2 zurück, 1 gibt 3 zurück und so weiter. Ich sehe kein Problem.
Meilen
Ich meinte, Sie müssen ein Byte für diese Antwort speichern, um zu gewinnen, weil ich Sie mit 6 Byte gebunden habe, Ihre Antwort selbst ist in Ordnung.
Magic Octopus Urn
5

MATL , 9 Bytes

1i:"EZq0)

Eingänge n , Ausgänge a ( n ), 1-indiziert.

Probieren Sie es online!

Erläuterung

1       % Push 1
i       % Push input n
:"      % Do the following that many times
  E     %   Multiply by 2
  Zq    %   Primes up to that
  0)    %   Get last entry
        % End (implicit). Display (implicit)
Luis Mendo
quelle
5

Stax , 10 Bytes

ü☼┌τ,æ▒ìn(

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 eine 5 6-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.

ODH{|p}{vgs

Die Umsetzung der Problemstellung ist relativ unkompliziert. Das einzig interessante daran ist die Verwendung der gsGeneratorform. 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 :pAnweisung verwendet.

O               Push integer 1 underneath the input number.
 D              Pop the input and repeat the rest of the program that many times.
  H             Double number.
   {|p}         Predicate block: is prime?
       {vgs     Decrement until the predicate is satisfied.
                Output is implicitly printed.

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.

rekursiv
quelle
Schöne Sprache! Ich habe es zu meiner Liste des langs Golfens hinzugefügt . Lassen Sie mich wissen, wenn Sie etwas falsch sehen oder wenn Sie noch etwas hinzufügen möchten.
ETHproductions
@ETHproductions: Schön, danke! Wenn es Ihnen nichts ausmacht, können Sie die Interpreter-URL in staxlang.xyz ändern. Ich habe beschlossen, eine Domain dafür zu bekommen.
rekursive
1
Wow, eine ganze Domain nur für eine Golfsprache? Lucky esolang;) Aktualisiert!
ETHproductions
@recursive WOW, 1,99 US-Dollar für jede xyz-Domain? Ich bin in.
Magic Octopus Urn
4

Python 2 , 63 Bytes

r=m=k=P=2
while k:
 P*=k;k+=1
 if k>m:print r;m=r*2
 if P%k:r=k

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 rund die Verdopplungsgrenze m.

Dabei werden P*=knicht P*=k*kwie üblich zwei Bytes gespeichert , da der einzige Effekt darin besteht, zu behaupten, dass 4 eine Primzahl ist, und die Folge der Verdopplung diese verfehlt.

xnor
quelle
4

CJam (15 Bytes)

2{2*{mp},W=}qi*

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 :

2{2*,W%{mp}=}qi*
Peter Taylor
quelle
4

Japt , 16 14 13 12 Bytes

Zwei 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().

_ôZ fj Ì}g°U

Versuch es

                 :Implicit input of integer U
_       }g       :Starting with the array [0,1] take the last element (Z),
                 :pass it through the following function
                 :and push the returned value to the array
 ôZ              :  Range [Z,Z+Z]
    fj           :  Filter primes
       Ì         :  Get the last item
          °U     :Repeat that process U+1 times and return the last element in the array

Erste N Begriffe

ÆV=ôV fj ̪2

Versuch es

                 :Implicit input of integer U
                 :Also makes use of variable V, which defaults to 0
Æ                :Create range [0,U) and pass each through a function
  ôV             :  Range [V,V+V]
     fj          :  Filter primes
        Ì        :  Get the last item
         ª2      :  Logical OR with 2, because the above will return undefined on the first iteration
 V=              :  Assign the result of the above to V
Zottelig
quelle
2

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).

k=2
while 1:
 print k;k+=k
 while any(k%u<1for u in range(2,k)):k-=1

Probieren Sie es online!

Python 3 , 90 Bytes

Gibt den n- ten Term zurück.

f=lambda n,i=1,p=1:n*[0]and p%i*[i]+f(n-1,i+1,p*i*i) 
a=lambda n:n and f(2*a(n-1))[-1]or 1

Probieren Sie es online!

Mr. Xcoder
quelle
2

C (GCC) , 97 87 86 80 79 Bytes

  • Durch Inlining einer Nicht-Primalitätsprüffunktion wurden zehn Bytes gespart P in die Hauptschleife eingefügt haben.
  • Ein Byte durch Verschieben von gespeichert printf Anrufs wurde .
  • 6 Bytes gespart durch Rückgabe der i -ten Sequenzeintrag (0-indiziert) zurückgegeben haben, anstatt einen nie endenden Stream auszugeben.
  • Dank ceilingcat wurde ein Byte gespeichert .
f(p,r,i,m,e){for(r=2;p--;)for(e=0,i=r+r;e=m=!e;r=i--)for(;i-++m;e=e&&i%m);p=r;}

Probieren Sie es online!

Jonathan Frech
quelle
@ceilingcat Vielen Dank.
Jonathan Frech
1

Attache , 38 Bytes

{If[_,Last[Series[Prime,2*$[_-1]]],2]}

Probieren Sie es online!

0-basiert; gibt das zurückn th Bertrand prime zurück.

Es gibt derzeit kein eingebautes Element, um die vorherigen / nächsten Primzahlen zu finden, daher verwende ich das Serieseingebaute Element, um alle Primzahlen bis zu zu berechnen 2*$[_-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.

Conor O'Brien
quelle
1

Perl 6 , 35 Bytes

2,{(2*$_,*-1...&is-prime).tail}...*

Probieren Sie es online!

Dieser Ausdruck ist eine unendliche Liste von Bertrand-Primzahlen.

Sean
quelle
1

Netzhaut , 39 Bytes

.K`_
"$+"{`_
__
+`^(?=(..+)\1+$).

*\`_

Probieren Sie es online! Erläuterung:

.K`_

Beginnen Sie mit 1.

"$+"{`

Wiederholen Sie die Schleife mit dem Eingang als Schleifenzahl.

_
__

Verdoppeln Sie den Wert.

+`^(?=(..+)\1+$).

Finde die höchste Primzahl, die kleiner als der Wert ist.

*\`_

Drucke es aus.

Neil
quelle
0

Ruby , 51 + 7 (-rprime) = 58 Bytes

->n{x=2
n.times{x=(x..2*x).select(&:prime?)[-1]}
x}

Probieren Sie es online!

Eine Lamba, ndie die nthBertrand-Primzahl mit dem Index 0 annimmt und zurückgibt . Hier ist nicht viel, aber lass es mich trotzdem loswerden:

->n{
  x=2                       # With a starting value of 2
  n.times{                  # Repeat n times:
    x=(x..2*x)              # Take the range from x to its double
      .select(&:prime?)[-1] # Filter to only primes, and take the last
  }
  x                         # Return
}

Ruby , 48 + 7 = 55 Bytes

x=2
loop{puts x
x*=2
loop{(x-=1).prime?&&break}}

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:

x=2
loop{
  puts x
  x*=2
  loop{
    (x-=1).prime? && break
  }
}
benj2240
quelle
0

APL (Dyalog Extended) , 12 Byte

Nimmt Eingaben vom Benutzer als N und gibt das N-te Element der Sequenz zurück (0-indiziert).

42×⍵}⍣⎕⊢2

Probieren Sie es online!

Erläuterung:

42×⍵}⍣⎕⊢2  Full program
              Get input from user - call it 'N'
          2  Repeat the left function N times, beginning with 2
    2×⍵        Double the function input
 ¯4           Find the largest prime less than above
voidhawk
quelle
0

R 87 Bytes

Gegebene nLeistungena(n)

j=scan();n=2;while(j-1){for(i in (n+1):(2*n)){n=ifelse(any(i%%2:(i-1)<1),n,i)};j=j-1};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.

Sumner18
quelle