Postulat Bertranda stwierdza, że ​​dla każdej liczby całkowitej n ≥ 1 istnieje co najmniej jedna liczba pierwsza p, tak że n <p ≤ 2n . Aby zweryfikować to twierdzenie dla n <4000 , nie musimy sprawdzać 4000 przypadków: sztuczka Landaua mówi, że wystarczy sprawdzić, czy

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 5003

wszystkie są najważniejsze. Ponieważ każda z tych liczb jest mniejsza niż dwukrotność swojego poprzednika, każdy przedział {y: n <y ≤ 2n} zawiera co najmniej jedną z tych liczb pierwszych.

Ta sekwencja liczb to liczby pierwsze Bertranda (OEIS A006992) i są one zdefiniowane w następujący sposób:

a(1) = 2
a(n) = largest prime below 2a(n-1)

Wyzwanie

Zaimplementuj tę sekwencję. Możesz pisać

• funkcja lub program, który podał jakieś n, zwraca a (n) (indeksowane 0 lub 1),
• funkcja lub program, który podał jakieś n, zwraca pierwsze n (lub n-1 lub n + 1 ) wpisów tej sekwencji,
• nieskończona lista lub strumień, generator lub podobny odpowiednik w twoim języku.

Oktawa , 32 bajty

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

Powoduje drukowanie wartości w nieskończoność (każda wartość poprzedza k =).

Wypróbuj online!

Oktawa , 42 bajty

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

Pobiera n jako dane wejściowe i wyjściowe n pierwszych wartości (każda wartość jest poprzedzona znakiem k =).

Wypróbuj online!

Oktawa , 51 bajtów

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

Podobne do odpowiedzi MATL Luisa Mendo . Przyjmuje n jako dane wejściowe i wyjściowe a (n) (indeksowane 1).

Wypróbuj online!

Oktawa , 60 bajtów

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

Przyjmuje n jako dane wejściowe i wyjściowe a (n) (indeksowane 1).

Wypróbuj online!

J , 11 bajtów

_4&(p:+:)2:

Wypróbuj online!

0-indeksowane.

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

Wolfram Language (Mathematica) , 27 bajtów

Oszczędność jednego bajtu dzięki Martinowi Enderowi.

0-indeksowane.

Nest[-NextPrime[-2#]&,2,#]&

Wypróbuj online!

05AB1E , 14 7 6 bajtów

$F·.ØØ

Wypróbuj online!

Odpowiedź z indeksowaniem 1 (chyba że 0 ma dać wynik 1), wyjaśnienie:

$       # 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.

Jest indeksowany 1, ponieważ wszystkie iteracje mają iterację „obojętną” n=1.

Haskell , 50 bajtów

f p|sum(gcd p<$>[1..p-1])<p=p:f(2*p)|1>0=f$p-1
f 2

Wypróbuj online!

Generuje nieskończoną listę.

Haskell , 40 bajtów?

f p|mod(2^p-2)p<1=p:f(2*p)|1>0=f$p-1
f 2

Wypróbuj online!

Działa to, jeśli liczby pierwsze Bertranda nie zawierają żadnych pseudopierwszych liczb Fermata dla 2 .

Galaretka , 6 bajtów

2ḤÆp$¡

Wypróbuj online!

0-indeksowane.

Wyjaśnienie

2ḤÆp$¡  Main link. Input: n
2       Constant 2
    $¡  Repeat n times
 Ḥ        Double
  Æp      Find the largest prime less than the double

MATL , 9 bajtów

1i:"EZq0)

Wejścia n , wyjścia a ( n ), 1-indeksowane.

Wypróbuj online!

Wyjaśnienie

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)

Stax , 10 bajtów

ü☼┌τ,æ▒ìn(

Uruchom przypadki testowe

Ten problem ujawnił błąd w implementacji stax :p, który jest instrukcją, która dostaje największą liczbę pierwszą mniej niż jego wkład. Gdyby działało poprawnie, istniałoby rozwiązanie 5 6 bajtów. Ale niestety tak nie jest i nie ma. Jako twórca języka naprawię go, ale po opublikowaniu problemu wydaje się to tanie.

Tak czy inaczej, tutaj jest odpowiednia reprezentacja programu ascii powyżej.

ODH{|p}{vgs

Jest to stosunkowo prosta implementacja opisu problemu. Jedyną rzeczą, która może być w tym interesująca, jest użycie gsformy generatora. Generatory to rodzina konstrukcji, które łączą warunek początkowy, transformację i filtr, aby uzyskać jedną lub więcej satysfakcjonujących wartości. W takim przypadku jest on używany zamiast zepsutej :pinstrukcji.

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.

Edycja: oto 6-bajtowe rozwiązanie, ale wymaga poprawki, która została zastosowana dopiero po opublikowaniu tego wyzwania.

Python 2 , 63 bajty

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

Wypróbuj online!

Drukuje na zawsze.

Korzysta z generatora liczb pierwszych Twierdzenia Wilsona, nawet jeśli generowanie liczb pierwszych do przodu jest niezręczne z powodu tego problemu. Śledzi aktualnie widzianą największą rliczbę pierwszą i podwójną granicę m.

Zapisywane są dwa bajty, P*=ka nie P*=k*kjak zwykle, ponieważ jedynym efektem jest twierdzenie, że 4 jest liczbą pierwszą, a sekwencja podwojenia go pomija.

CJam (15 bajtów)

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

Demo online . Zauważ, że jest to indeksowane na 0.

Bardziej efektywnym podejściem byłoby przeszukiwanie do tyłu, ale wymaga to jeszcze jednego znaku, ponieważ nie można użyć niejawnego ,(zakres):

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

Japt , 16 14 13 12 bajtów

Dwa rozwiązania w cenie jednego, oba indeksowane 1.

N-ty okres

Wreszcie wyzwanie, które mogę napisać działające rozwiązanie F.g().

_ôZ fj Ì}g°U

Spróbuj

                 :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

Pierwsze N ​​warunków

ÆV=ôV fj ̪2

Spróbuj

                 :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

Pari / GP , 34 bajty

a(n)=if(n<2,2,precprime(2*a(n-1)))

Wypróbuj online!

Python 2 , 64 bajty

n=2
while 1:
 if all(n%i for i in range(2,n)):print n;n*=2
 n-=1

Wypróbuj online! Drukuje sekwencję w nieskończoność

Haskell , 58 bajtów

a 1=2
a n=last[p|p<-[2..2*a(n-1)],all((>0).mod p)[2..p-1]]

Wypróbuj online!

Python 2 , 68 bajtów

Drukuje sekwencję w nieskończoność (musisz kliknąć „Uruchom” drugi raz, aby zatrzymać wykonywanie).

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

Wypróbuj online!

Python 3 , 90 bajtów

Zwraca n- ^ty termin.

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

Wypróbuj online!

C (gcc) , 97 87 86 80 79 bajtów

• Zaoszczędzono dziesięć bajtów, wstawiając funkcję sprawdzania nie-pierwotności Pdo głównej pętli.
• Zapisano bajt, przenosząc printfpołączenie.
• Zapisano sześć bajtów, zwracając iwpis -tej sekwencji (indeksowany 0) zamiast wysyłania niekończącego się strumienia.
• Oszczędność bajtu dzięki pułapkowi cat .

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

Wypróbuj online!

Attache , 38 bajtów

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

Wypróbuj online!

Na podstawie 0; zwraca nliczbę pierwszą Bertrand.

Obecnie nie ma wbudowanego, aby znaleźć poprzednie / następne liczby pierwsze, więc używam Serieswbudowanego, aby obliczyć wszystkie liczby pierwsze do 2*$[_-1]. To ostatnie wyrażenie używa niejawnej rekurencji (powiązanej z $), aby łatwo zdefiniować relację powtarzalności. Warunek if służy do określenia warunku podstawowego.

Perl 6 , 35 bajtów

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

Wypróbuj online!

To wyrażenie jest nieskończoną listą liczb pierwszych Bertranda.

Siatkówka , 39 bajtów

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

*\`_

Wypróbuj online! Wyjaśnienie:

.K`_

Zacznij od 1.

"$+"{`

Powtórz pętlę, używając danych wejściowych jako liczby pętli.

_
__

Podwój wartość.

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

Znajdź najwyższą liczbę pierwszą mniejszą niż wartość.

*\`_

Wydrukuj to.

Ruby , 51 + 7 (-rprime) = 58 bajtów

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

Wypróbuj online!

Lamba przyjmuje ni zwraca liczbę nthpierwszą Bertrand, indeksowaną 0. Nie ma tu wiele, ale i tak pozwolę sobie na to:

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

Rubinowy , 48 + 7 = 55 bajtów

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

Wypróbuj online!

Dla zabawy oto rozwiązanie z nieskończoną pętlą. Drukuje bez przerwy i wymaga przerwania. W zależności od tego, kiedy dokładnie przerwiesz, możesz, ale nie musi zobaczyć wyjście. Nie golfowany:

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

APL (Dyalog Extended) , 12 bajtów

Pobiera dane wejściowe od użytkownika jako N, zwraca N-ty element sekwencji (indeksowany 0).

{¯4⍭2×⍵}⍣⎕⊢2

Wypróbuj online!

Wyjaśnienie:

{¯4⍭2×⍵}⍣⎕⊢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

R , 87 bajtów

Podane nwynikia(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

Wypróbuj online!

Nadal pracuję nad „Biorąc pod uwagę wyjście n a (1), a (2) ... a (n)”. Myślałem, że mogę nieco zmodyfikować ten kod, ale wydaje się to trudniejsze.