Le postulat de Bertrand indique que pour chaque entier n ≥ 1, il y a au moins un premier p tel que n <p ≤ 2n . Pour vérifier ce théorème pour n <4000 nous n'avons pas à vérifier 4000 cas: L' astuce de Landau dit qu'il suffit de vérifier que

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

sont tous premiers. Parce que chacun de ces nombres est inférieur au double de son prédécesseur, chaque intervalle {y: n <y ≤ 2n} contient au moins un de ces nombres premiers.

Cette séquence de nombres sont les Bertrand Primes (OEIS A006992) et ils sont définis comme suit:

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

Défi

Implémentez cette séquence. Vous pouvez écrire

• une fonction ou un programme qui, étant donné n, renvoie a (n) (0 ou 1 indexé),
• une fonction ou un programme qui, étant donné n, renvoie les n premières entrées (ou n-1 ou n + 1 ) de cette séquence,
• une liste ou un flux infini ou un générateur ou équivalent similaire dans votre jauge.

Octave , 32 octets

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

Continue à imprimer les valeurs indéfiniment (chaque valeur est précédée de k =).

Essayez-le en ligne!

Octave , 42 octets

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

Prend n comme entrée et sort les n premières valeurs (chaque valeur est précédée de k =).

Essayez-le en ligne!

Octave , 51 octets

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

Similaire à la réponse MATL de Luis Mendo . Prend n comme entrée et produit a (n) (indexé 1).

Essayez-le en ligne!

Octave , 60 octets

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

Prend n comme entrée et produit a (n) (indexé 1).

Essayez-le en ligne!

J , 11 octets

_4&(p:+:)2:

Essayez-le en ligne!

0 indexé.

_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 octets

Sauvegardé d'un octet grâce à Martin Ender.

0 indexé.

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

Essayez-le en ligne!

05AB1E , 14 7 6 octets

$F·.ØØ

Essayez-le en ligne!

Réponse indexée 1 (sauf si 0 est supposé produire 1), explication:

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

Il est indexé 1 car toutes les itérations ont une itération «factice» avec n=1.

Haskell , 50 octets

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

Essayez-le en ligne!

Génère une liste infinie.

Haskell , 40 octets?

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

Essayez-le en ligne!

Cela fonctionne si les nombres premiers de Bertrand ne contiennent aucun pseudoprime de Fermat pour 2 .

Gelée , 6 octets

2ḤÆp$¡

Essayez-le en ligne!

0 indexé.

Explication

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

MATL , 9 octets

1i:"EZq0)

Entrées n , sorties a ( n ), 1 indexées.

Essayez-le en ligne!

Explication

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 octets

ü☼┌τ,æ▒ìn(

Exécuter des cas de test

Ce problème a révélé un bogue dans l'implémentation de stax :p, qui est une instruction qui obtient le plus grand nombre inférieur à son entrée. Si cela fonctionnait correctement, il y aurait une solution de 5 à 6 octets. Mais hélas non, et il n'y en a pas. En tant que créateur de la langue, je vais le réparer, mais il semble plutôt bon marché de le réparer et de l'utiliser après la publication du problème.

Quoi qu'il en soit, voici la représentation ascii correspondante du programme ci-dessus.

ODH{|p}{vgs

Il s'agit d'une implémentation relativement simple de l'énoncé du problème. La seule chose éventuellement intéressante à ce sujet est l'utilisation du gsformulaire générateur. Les générateurs sont une famille de constructions qui combinent une condition initiale, une transformation et un filtre pour produire une ou plusieurs valeurs satisfaisantes. Dans ce cas, il est utilisé à la place de l' :pinstruction cassée .

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.

Modifier: voici la solution à 6 octets, mais elle nécessite une correction de bogue qui n'a été appliquée qu'après la publication de ce défi.

Python 2 , 63 octets

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

Essayez-le en ligne!

Imprime pour toujours.

Utilise le générateur principal de théorème de Wilson, même si la génération de nombres premiers vers l'avant est maladroite pour ce problème. Suit le plus grand nombre premier observé ret la limite de doublement m.

Deux octets sont enregistrés en faisant P*=kplutôt que P*=k*kd'habitude, car le seul effet est de prétendre que 4 est premier, et la séquence de doublage le manque.

CJam (15 octets)

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

Démo en ligne . Notez qu'il s'agit d'un index 0.

Une approche plus efficace serait de rechercher en arrière, mais cela nécessite un caractère de plus car il ne peut pas utiliser implicite ,(plage):

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

Japt , 16 14 13 12 octets

Deux solutions pour le prix d'une, toutes deux indexées.

Nième terme

Enfin, un défi que je peux écrire une solution de travail à utiliser F.g().

_ôZ fj Ì}g°U

Essayez-le

                 :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

Premiers N termes

ÆV=ôV fj ̪2

Essayez-le

                 :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 octets

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

Essayez-le en ligne!

Python 2 , 64 octets

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

Essayez-le en ligne! Imprime la séquence indéfiniment

Haskell , 58 octets

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

Essayez-le en ligne!

Python 2 , 68 octets

Imprime la séquence indéfiniment (vous devez cliquer sur "Exécuter" la deuxième fois pour arrêter l'exécution).

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

Essayez-le en ligne!

Python 3 , 90 octets

Renvoie le n ^ème terme.

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

Essayez-le en ligne!

C (gcc) , 97 87 86 80 79 octets

• Enregistrement de dix octets en insérant une fonction de vérification de non-primalité Pdans la boucle principale.
• Sauvegardé un octet en déplaçant le printf appel.
• Enregistré six octets en retournant le i -ième entrée de séquence (indexée 0) au lieu de produire un flux sans fin.
• Enregistré un octet grâce au plafond .

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

Essayez-le en ligne!

Attaché , 38 octets

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

Essayez-le en ligne!

Basé sur 0; renvoie len th Bertrand prime.

Il n'y a actuellement aucune fonction intégrée pour trouver les nombres premiers précédents / suivants, donc j'utilise la fonction Seriesintégrée pour calculer tous les nombres premiers jusqu'à 2*$[_-1]. Cette dernière expression utilise la récursivité implicite (liée à $) pour définir facilement la relation de récurrence. La condition if est utilisée pour déterminer une condition de base.

Perl 6 , 35 octets

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

Essayez-le en ligne!

Cette expression est une liste infinie de nombres premiers de Bertrand.

Rétine , 39 octets

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

*\`_

Essayez-le en ligne! Explication:

.K`_

Commencez par 1.

"$+"{`

Répétez la boucle en utilisant l'entrée comme nombre de boucles.

_
__

Doublez la valeur.

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

Trouvez le plus haut prime inférieur à la valeur.

*\`_

Imprimez le.

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

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

Essayez-le en ligne!

Un lamba acceptant net renvoyant le nthprime de Bertrand, indexé 0. Il n'y a pas grand-chose ici, mais permettez-moi de le dissoudre quand même:

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

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

Essayez-le en ligne!

Pour le plaisir, voici une solution en boucle infinie. Il imprime au fur et à mesure et nécessite une interruption. En fonction de l'heure exacte à laquelle vous interrompez, vous pouvez voir ou non la sortie. Non golfé:

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

APL (Dyalog Extended) , 12 octets

Prend l'entrée de l'utilisateur comme N, retourne le Nième élément de la séquence (indexé 0).

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

Essayez-le en ligne!

Explication:

{¯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 octets

nRésultats donnésa(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

Essayez-le en ligne!

Je travaille toujours sur "Étant donné n sortie a (1), a (2) ... a (n)". Je pensais que je pouvais juste modifier légèrement ce code, mais cela semble plus difficile que cela.