Desde Euclides, hemos sabido que hay infinitos números primos. El argumento es por contradicción: si solo hay muchos, digamos , entonces seguramente no es divisible por ninguno de estos primos, por lo que su factorización prima debe producir un nuevo primo que no estaba en la lista. Entonces, la suposición de que solo existen primos finitos es falsa. $p_1,p_2,...,p_n$ $m:=p_1\cdot p_2\cdot...\cdot p_n+1$

Ahora supongamos que es el único primo. El método de arriba produce como un nuevo (posible) primo. Aplicar el método nuevamente produce , y luego , luego , entonces ambos y son primos nuevos, etc. En el caso de que obtengamos un número compuesto, simplemente tomamos el primo menos nuevo. Esto da como resultado A000945 . $2$ $2+1=3$ $2\cdot 3+1=7$ $2\cdot 3\cdot 7+1=43$ $2\cdot 3\cdot 7\cdot 43+1=13\cdot 139$ $13$ $139$

Reto

Dado un primer $p_1$ y un entero $n$ calcular el $n$ -ésimo término $p_n$ de la secuencia definida como sigue:

{pags}_{norte} : = min (factores primos ({pags}_{1} \cdot {pags}_{2} \cdot . . . \cdot {pags}_{norte - 1} + 1))

$p_n := \min(\operatorname{primefactors}(p_1\cdot p_2\cdot ... \cdot p_{n-1} + 1))$

Estas secuencias se conocen como secuencias de Euclid-Mullin .

Ejemplos

Para : $p_1 = 2$

1 2
2 3
3 7
4 43
5 13
6 53
7 5
8 6221671
9 38709183810571

Para ( A051308 ): $p_1 = 5$

1 5
2 2
3 11
4 3
5 331
6 19
7 199
8 53
9 21888927391

Para ( A051330 ) $p_1 = 97$

code-golf sequence integer primes factoring falla
fuente

10

JavaScript (ES6), 45 44 bytes

Toma la entrada como (n)(p1), donde está indexada a 0. $n$

n=>g=(p,d=2)=>n?~p%d?g(p,d+1):--n?g(p*d):d:p

Pruébalo en línea!

Comentado

n =>                // n = 0-based index of the requested term
  g = (             // g is a recursive function taking:
    p,              //   p = current prime product
    d = 2           //   d = current divisor
  ) =>              //
    n ?             // if n is not equal to 0:
      ~p % d ?      //   if d is not a divisor of ~p (i.e. not a divisor of p + 1):
        g(p, d + 1) //     increment d until it is
      :             //   else:
        --n ?       //     decrement n; if it's still not equal to 0:
          g(p * d)  //       do a recursive call with the updated prime product
        :           //     else:
          d         //       stop recursion and return d
    :               // else:
      p             //   don't do any recursion and return p right away

Arnauld
fuente

9

05AB1E , 6 bytes

Esto produce un flujo de salida infinito.

λλP>fW

Pruébalo en línea! (el enlace incluye una versión ligeramente modificada λ£λP>fW, que en su lugar genera los primeros términos) $n$

Explicación

Muy sencillo Dado y , el programa hace lo siguiente: $p_1$ $n$

Comienza con como parámetro inicial para la secuencia infinita (que se genera utilizando la primera ) y comienza un entorno recursivo que genera un nuevo término después de cada interacción y lo agrega a la secuencia. $p_1$ λ
El segundo λ, que ahora se usa dentro del entorno recursivo, cambia su funcionalidad: ahora, recupera todos los elementos generados previamente (es decir, la lista ), donde representa el número de iteración actual. $[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]$ $n$
El resto es trivial: Ptoma el producto ( $\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}$ ), >agrega uno a este producto y fWrecupera el factor primo mínimo.

Sr. Xcoder
fuente

6

J , 15 bytes

-10 bytes gracias a millas!

Devolviendo la secuencia hasta n (indexado a cero) - gracias a @miles

(,0({q:)1+*/)^:

Pruébalo en línea!

J , 25 bytes

Devuelve el nelemento th

_2{((],0{[:q:1+*/@])^:[])

Pruébalo en línea!

Galen Ivanov
fuente

1

(,0({q:)1+*/)^:para 15 bytes, devolviendo la secuencia hasta n(indexado a cero)

millas

@miles ¡Gracias!

Galen Ivanov

Muy agradable. @miles, ¿qué está pasando allí gramaticalmente? ponemos un verbo y una conjunción juntos y recuperamos un verbo diádico. Pensé que verb conj producía un adverbio .

Jonás

1

@ Jonás es un truco que aprendí del golf. Creo que es una de las reglas de análisis de mayor edad que sigue siendo válido

millas

@miles Me acabo de dar cuenta de que es un adverbio (o anuncio). Se modifica el sustantivo a su izquierda, que "agregados" a la derecha de la ^:, y después de que se convierte en un verbo que se aplica a la arg derecha. Creo que eso es lo que está sucediendo gramaticalmente.

Jonás

5

Python 2 , 56 bytes

i=input();k=1
while 1:
 k*=i;print i;i=2
 while~k%i:i+=1

Pruébalo en línea!

Comentado

i=input() # the initial prime
k=1       # the product of all previous primes
while 1:  # infinite loop
 k*=i     # update the product of primes
 print i  # output the last prime
 i=2      # starting at two ...
 while~k%i: # find the lowest number that divides k+1
  i+=1
            # this our new prime

Pruébalo en línea!

ovs
fuente

Acabo de empezar con Python, pero es lo que necesita int(input())de otro modo ies un str?

Anthony

2

En Python 3 esto sería cierto ya que input()siempre devuelve cadenas. En Python 2 input()intenta evaluar la entrada. Estoy usando Python 2 en este caso porque el código resultante es un poco más corto. Para el código real , debe intentar usar Python 3, ya que es la versión más nueva y más compatible de Python.

ovs

¿Cómo termina esto después de n pasos?

sintax

@sintax emite la secuencia para un p1 dado indefinidamente, según lo permitido por las reglas de secuencia predeterminadas .

ovs

4

Jalea , 8 bytes

P‘ÆfṂṭµ¡

$P_0$ $n$ $P_0$ $P_n$ n=0

Pruébalo en línea!

¿Cómo?

P‘ÆfṂṭµ¡ - Link: integer, p0; integer n
      µ¡ - repeat the monadic chain to the left n times, starting with x=p0:
P        -   product of x (p0->p0 or [p0,...,pm]->pm*...*p0)
 ‘       -   increment
  Æf     -   prime factors
    Ṃ    -   minimum
     ṭ   -   tack
         - implicit print

Jonathan Allan
fuente

3

05AB1E , 8 bytes

GDˆ¯P>fß

$n$ $p$

$n\geq9$ $p=2$ $p=5$ f

Explicación:

G         # Loop (implicit input) n-1 amount of times:
 Dˆ       #  Add a copy of the number at the top of the stack to the global array
          #  (which will take the second input p implicitly the first iteration)
   ¯      #  Push the entire global array
    P     #  Take the product of this list
     >    #  Increase it by 1
      f   #  Get the prime factors of this number (without counting duplicates)
       ß  #  Pop and only leave the smallest prime factor
          # (after the loop: implicitly output the top of the stack as result)

Kevin Cruijssen
fuente

λλP>fWλ£λP>fW

n

$n$

n^{th}

$n^{\text{th}}$ £

@ Mr.Xcoder "¡ Si tan solo tuviéramos una bandera como £para el último elemento! ", .£¿ Como ? ;) EDITAR: En realidad, no funciona exactamente como £para las listas ... usando una lista como [1,2]con .£resultados en dos elementos sueltos con los últimos 1 y 2 elementos (es decir, se 12345convierte en [5,45]lugar de [45,3]o [3,45]con 12S.£) ..

Kevin Cruijssen

Umm, no, no veo cómo λ.£debería funcionar. Usé flag como una función adicional asociada con λ(ver esta conversación con Adnan ). Básicamente, quiero un indicador ètal que, cuando se ejecute λè...}, genere el enésimo elemento en lugar de la secuencia infinita (al igual λ£que funcionaría para generar los primeros n elementos).

Sr. Xcoder

@ Mr.Xcoder Ah, lo siento, has utilizado el £entorno recursivo. Sí, entonces de λ.£hecho no va a funcionar, mi mal. Buen 6 byter independientemente. Ahora solo tiene que esperar la respuesta de @flawr si está permitido o no (probablemente lo esté).

Kevin Cruijssen

3

Japt , 12 11 bytes

Luchó por hacer esto bien, por lo que puede haberse perdido algo que se puede jugar al golf.

Toma ncomo la primera entrada y p1, como una matriz singleton, como la segunda. Devuelve los primeros ntérminos. Cambie ha gpara devolver el ntérmino indexado th 0 en su lugar.

@Z×Ä k Î}hV

Intentalo

@Z×Ä k Î}hV     :Implicit input of integer U=n & array V=[p1]
@               :Function taking an array as an argument via parameter Z
 Z×             :  Reduce Z by multiplication
   Ä            :  Add 1
     k          :  Prime factors
       Î        :  First element
        }       :End function
         hV     :Run that function, passing V as Z, and
                : push the result to V.
                : Repeat until V is of length U

Lanudo
fuente

3

Retina , 56 bytes

,|$
$*
"$&"{~`.+¶
$$¶_
)`\b(__+?)\1*$
$.1$*
1A`
.$

\*
,

Pruébalo en línea! Toma datos como el número de términos nuevos que se agregarán en la primera línea y los términos semilla en la segunda línea. Nota: Se vuelve muy lento ya que usa factorización unaria, por lo que necesita crear una cadena de la longitud relevante. Explicación:

,|$
$*

Reemplace las comas en los términos semilla con *sy agregue a *. Esto crea una expresión Retina para una cadena de longitud del producto de los valores.

"$&"{
)`

Repita el bucle el número de veces dado por la primera entrada.

~`.+¶
$$¶_

Reemplace temporalmente el número en la primera línea con a $y anteponga a _a la segunda línea, luego evalúe el resultado como un programa Retina, agregando así una cadena de _s de longitud 1 más que el producto de los valores.

\b(__+?)\1*$
$.1$*

Encuentre el factor no trivial más pequeño del número en decimal y agregue un *listo para el siguiente ciclo.

1A`

Eliminar la entrada de iteración.

.$

Eliminar el último *.

\*
,

Reemplace los *s restantes con ,s.

Neil
fuente

2

JavaScript (Node.js) , 54 bytes

f=(p,n,P=p,F=n=>-~P%n?F(n+1):n)=>--n?f(p=F(2),n,P*p):p

Pruébalo en línea!

Sin golf

F=(p,n=2)=>            // Helper function F for finding the smallest prime factor
  p%n                  //   If n (starting at 2) doesn't divide p:
    ?F(n+1)            //     Test n+1 instead
    :n                 //   Otherwise, return n
f=(p,n,P=p)=>          // Main function f:
  --n                  //   Repeat n - 1 times:
    ?f(p=F(P+1),n,P*p) //     Find the next prime factor and update the product
    :p                 //   Return the last prime

Herman L
fuente

2

bash + GNU coreutils, 89 bytes

IFS=\*;n=$1;shift;for((;++i<n;));{ set $@ `factor $["$*+1"]|cut -d\  -f2`;};echo ${@: -1}

TIO

Nahuel Fouilleul
fuente

2

Ruby 2.6, 51 bytes

f=->s,n{[s,l=(2..).find{|d|~s%d<1}][n]||f[l*s,n-1]}

(2..), el rango infinito a partir de 2, todavía no es compatible con TIO.

Esta es una función recursiva que toma un valor inicial s(puede ser primo o compuesto), lo devuelve cuando n = 0 (editar: tenga en cuenta que esto significa que está indexado a cero), devuelve el menor número lque es mayor que 1 y se divide -(s+1)cuando n = 1, y de lo contrario se repite con s=l*sy n=n-1.

histocrat
fuente

1

Probablemente deberías mencionar que estás haciendo indexado a cero; Lo reemplacé (2..)con 2.step(solo 1 byte más) para permitir que funcione en TIO y todo estaba apagado por uno. Pruébalo en línea!

Value Ink el

2

APL (Dyalog Extended) , 15 bytes

Esta es una aplicación bastante sencilla del algoritmo que utiliza extendidas de factores primos muy votos orden interna, ⍭. Pruébalo en línea!

{⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕

Explicación

{⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕

             ⊢⎕  First get the first prime of the sequence S from input.
{         }⍣⎕    Then we repeat the code another input number of times.
     1+×/⍵       We take the product of S and add 1.
    ⍭            Get the prime factors of product(S)+1.
   ⊃             Get the first element, the smallest prime factor of prod(S)+1.
 ⍵,              And append it to S.

Sherlock9
fuente

1

Pari / GP , 47 bytes

(p,n)->s=1;for(i=2,n,s*=p;p=divisors(s+1)[2]);p

Pruébalo en línea!

alephalpha
fuente

1

Stax , 9 bytes

é|G╝╓c£¼_

Ejecutar y depurarlo

Toma y (indexado a cero) para la entrada. Produce .p₀np_n

recursivo
fuente

1

C (gcc) , 54 53 bytes

p;f(x,n){for(p=x;--n;p*=x)for(x=1;~p%++x;);return x;}

Pruébalo en línea!

-1 byte gracias a ceilingcat

wastl
fuente

1

Perl 6 , 33 32 bytes

-1 byte gracias a nwellnhof

{$_,{1+(2...-+^[*](@_)%%*)}...*}

Pruébalo en línea!

Bloque de código anónimo que toma un número y devuelve una lista perezosa.

Explicación:

{                              }  # Anonymous codeblock
                           ...*   # That returns an infinite list
 $_,                              # Starting with the input
    {                     }       # Where each element is
     1+(2...             )          # The first number above 2
                      %%*           # That cleanly divides
               [*](@_)                # The product of all numbers so far
            -+^                       # Plus one

Jo King
fuente

1

-+^[*](@_)Guarda un byte.

nwellnhof

0

Haskell , 49 bytes

g 1
g a b=b:g(a*b)([c|c<-[2..],1>mod(a*b+1)c]!!0)

Pruébalo en línea!

Devuelve la secuencia infinita como una lista perezosa.

Explicación:

g 1                                            -- Initialise the product as 1
g a b=                                         -- Given the product and the current number
       b:                                      -- Return the current number, followed by
         g                                     -- Recursively calliong the function with
          (a*b)                                -- The new product
               (                             ) -- And get the next number as
                [c|c<-[2..],             ]!!0  -- The first number above 2
                            1>mod       c      -- That cleanly divides
                                 (a*b+1)       -- The product plus one

Jo King
fuente

Infinitos primos

Reto

Ejemplos

Respuestas:

JavaScript (ES6), 45 44 bytes

Comentado

05AB1E , 6 bytes

Explicación

J , 15 bytes

J , 25 bytes

Python 2 , 56 bytes

Comentado

Jalea , 8 bytes

¿Cómo?

05AB1E , 8 bytes

Japt , 12 11 bytes

Retina , 56 bytes

JavaScript (Node.js) , 54 bytes

bash + GNU coreutils, 89 bytes

Ruby 2.6, 51 bytes

APL (Dyalog Extended) , 15 bytes

Pari / GP , 47 bytes

Stax , 9 bytes

C (gcc) , 54 53 bytes

Perl 6 , 33 32 bytes

Explicación:

Haskell , 49 bytes

Explicación: