El Postulado de Bertrand establece que por cada número entero n ≥ 1 hay al menos un primo p tal que n <p ≤ 2n . Para verificar este teorema para n <4000 no tenemos que verificar 4000 casos: el truco de Landau dice que es suficiente verificar que

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

son todos primos Debido a que cada uno de estos números es menos del doble de su predecesor, cada intervalo {y: n <y ≤ 2n} contiene al menos uno de esos números primos.

Esta secuencia de números son los Primas de Bertrand (OEIS A006992) y se definen de la siguiente manera:

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

Reto

Implementa esta secuencia. Puedes escribir

• una función o programa que da algo de n devuelve a (n) (0 o 1 indexado),
• una función o programa que da algo de n devuelve las primeras n (o n-1 o n + 1 ) entradas de esta secuencia,
• una lista infinita o corriente o generador o equivalente similar en su idioma.

Octava , 32 bytes

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

Sigue imprimiendo los valores indefinidamente (cada valor está precedido por k =).

Pruébalo en línea!

Octava , 42 bytes

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

Toma n como entrada y emite los n primeros valores (cada valor está precedido por k =).

Pruébalo en línea!

Octava , 51 bytes

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

Similar a la respuesta MATL de Luis Mendo . Toma n como entrada y produce a (n) (1 indexado).

Pruébalo en línea!

Octava , 60 bytes

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

Toma n como entrada y produce a (n) (1 indexado).

Pruébalo en línea!

J , 11 bytes

_4&(p:+:)2:

Pruébalo en línea!

0 indexado.

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

Guardado un byte gracias a Martin Ender.

0 indexado.

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

Pruébalo en línea!

05AB1E , 14 7 6 bytes

$F·.ØØ

Pruébalo en línea!

Respuesta indizada en 1 (a menos que se suponga que 0 debe generar 1), explicación:

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

Está indexado en 1 porque todas las iteraciones tienen una iteración 'ficticia' con n=1.

Haskell , 50 bytes

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

Pruébalo en línea!

Emite una lista infinita.

Haskell , 40 bytes?

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

Pruébalo en línea!

Esto funciona si los números primos de Bertrand no contienen pseudoprimos Fermat para 2 .

Jalea , 6 bytes

2ḤÆp$¡

Pruébalo en línea!

0 indexado.

Explicación

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

MATL , 9 bytes

1i:"EZq0)

Entradas n , salidas a ( n ), 1 indexado.

Pruébalo en línea!

Explicación

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 bytes

ü☼┌τ,æ▒ìn(

Ejecutar casos de prueba

Este problema ha expuesto un error en la implementación de stax :p, que es una instrucción que obtiene el mayor primo menos que su entrada. Si funcionara correctamente, habría una solución de 5 6 bytes. Pero, por desgracia, no lo hace, y no lo hay. Como creador del lenguaje, lo arreglaré, pero parece un poco barato arreglarlo y usarlo después de que se publicó el problema.

De todos modos, aquí está la representación ascii correspondiente del programa anterior.

ODH{|p}{vgs

Es una implementación relativamente sencilla de la declaración del problema. Lo único posiblemente interesante al respecto es el uso de la gsforma del generador. Los generadores son una familia de construcciones que combinan una condición inicial, una transformación y un filtro para producir uno o más valores satisfactorios. En este caso, se usa en lugar de la :pinstrucción rota .

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.

Editar: aquí está la solución de 6 bytes, pero requiere una corrección de errores que solo se aplicó después de publicar este desafío.

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

Pruébalo en línea!

Imprime para siempre.

Utiliza el generador principal de Theorem de Wilson aunque generar primos hacia adelante es complicado para este problema. Realiza un seguimiento del mayor número actual visto ry el límite de duplicación m.

Se guardan dos bytes en P*=klugar de P*=k*klo habitual, ya que el único efecto es afirmar que 4 es primo, y la secuencia de duplicación se pierde.

CJam (15 bytes)

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

Demo en línea . Tenga en cuenta que esto está indexado a 0.

Un enfoque más eficiente sería buscar hacia atrás, pero esto requiere un carácter más porque no puede usar implícito ,(rango):

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

Japt , 16 14 13 12 bytes

Dos soluciones por el precio de una, ambas indexadas.

Enésimo término

Finalmente, un desafío para el que puedo escribir una solución de trabajo F.g().

_ôZ fj Ì}g°U

Intentalo

                 :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

Primeros términos N

ÆV=ôV fj ̪2

Intentalo

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

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

Pruébalo en línea!

Python 2 , 64 bytes

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

Pruébalo en línea! Imprime la secuencia indefinidamente

Haskell , 58 bytes

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

Pruébalo en línea!

Python 2 , 68 bytes

Imprime la secuencia indefinidamente (debe hacer clic en "Ejecutar" la segunda vez para detener la ejecución).

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

Pruébalo en línea!

Python 3 , 90 bytes

Devuelve el n ^enésimo término.

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

Pruébalo en línea!

C (gcc) , 97 87 86 80 79 bytes

• Se guardaron diez bytes al incorporar una función de comprobación de no primalidad P en el bucle principal.
• Guardado un byte moviendo el printf llamada.
• Guardado seis bytes al devolver el i entrada de la secuencia número (indexada a 0) en lugar de generar una secuencia interminable.
• Guardado un byte gracias a ceilingcat .

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

Pruébalo en línea!

Adjunto , 38 bytes

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

Pruébalo en línea!

Basado en 0; devuelve el nth prime Bertrand.

Actualmente no hay una función integrada para encontrar los primos anteriores / siguientes, por lo que uso la función Seriesintegrada para calcular todos los primos hasta 2*$[_-1]. Esta última expresión utiliza la recursión implícita (vinculada a $) para definir fácilmente la relación de recurrencia. La condición if se usa para determinar una condición base.

Perl 6 , 35 bytes

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

Pruébalo en línea!

Esta expresión es una lista infinita de primos de Bertrand.

Retina , 39 bytes

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

*\`_

Pruébalo en línea! Explicación:

.K`_

Comience con 1.

"$+"{`

Repita el ciclo usando la entrada como el conteo del ciclo.

_
__

Duplica el valor.

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

Encuentre el primo más alto menos que el valor.

*\`_

Imprimirlo.

Ruby , 51 + 7 (-prime) = 58 bytes

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

Pruébalo en línea!

Una lamba que acepta ny devuelve la nthprima de Bertrand, indexada en 0. No hay mucho aquí, pero déjame quitarle el golf de todos modos:

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

Pruébalo en línea!

Por diversión, aquí hay una solución de bucle infinito. Imprime a medida que avanza y requiere una interrupción. Dependiendo de exactamente cuándo interrumpe, puede o no ver la salida. Sin golf:

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

APL (Dyalog Extended) , 12 bytes

Toma la entrada del usuario como N, devuelve el enésimo elemento de la secuencia (0 indexado).

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

Pruébalo en línea!

Explicación:

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

nResultados dadosa(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

Pruébalo en línea!

Todavía estoy trabajando en "Dada n salida a (1), a (2) ... a (n)". Pensé que podría modificar ligeramente este código, pero parece más difícil que eso.