Depuis Euclide, nous savons qu'il existe une infinité de nombres premiers. L'argument est en contradiction: S'il n'y a que nombre fini, disons que $p_1,p_2,...,p_n$ , alors sûrement $m:=p_1\cdot p_2\cdot...\cdot p_n+1$ n'est divisible par aucun de ces nombres premiers, donc sa factorisation en nombres premiers doit produire un nouveau nombre premier qui n'était pas dans la liste. Ainsi, l'hypothèse selon laquelle il n'existe que des nombres finis premiers est fausse.

Supposons maintenant que $2$ est le seul nombre premier. La méthode ci-dessus donne $2+1=3$ comme nouveau premier (possible). Appliquer à nouveau la méthode donne $2\cdot 3+1=7$ , puis $2\cdot 3\cdot 7+1=43$ , puis $2\cdot 3\cdot 7\cdot 43+1=13\cdot 139$ , donc et$13$$139$sont de nouveaux nombres premiers, etc. Dans le cas où nous obtenons un nombre composite, nous prenons simplement le moins nouveau nombre premier. Il en résulte A000945 .

Défi

Étant donné un nombre premier $p_1$ et un nombre entier $n$ calculer le $n$ -ième terme $p_n$ de la séquence définie comme suit:

Ces séquences sont appelées séquences Euclid-Mullin .

Exemples

Pour $p_1 = 2$ :

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

Pour $p_1 = 5$ ( A051308 ):

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

Pour $p_1 = 97$ ( A051330 )

1 97
2 2
3 3
4 11
5 19
6 7
7 461
8 719
9 5

JavaScript (ES6),  45  44 octets

Prend l'entrée comme (n)(p1), où $n$ est indexé 0.

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

Essayez-le en ligne!

Commenté

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

05AB1E , 6 octets

Cela produit un flux de sortie infini.

λλP>fW

Essayez-le en ligne! (le lien inclut une version légèrement modifiée λ£λP>fW, qui génère à la place les $n$ premiers termes)

Explication

Très simple. Étant donné $p_1$ et $n$ , le programme fait ce qui suit:

• Commence par $p_1$ comme paramètre initial pour le flux infini (qui est généré en utilisant le premier λ) et commence un environnement récursif qui génère un nouveau terme après chaque interaction et l'ajoute au flux.
• Le second λ, désormais utilisé dans l'environnement récursif, change de fonctionnalité: il récupère désormais tous les éléments générés précédemment (ie la liste $[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]$ ), où $n$ représente le numéro d'itération actuel.
• Le reste est trivial: Pprend le produit ( $\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}$ ), en >ajoute un à ce produit et fWrécupère le facteur premier minimum.

J , 15 octets

-10 octets grâce aux miles!

Renvoyer la séquence jusqu'à n (indexé zéro) - grâce à @miles

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

Essayez-le en ligne!

J , 25 octets

Renvoie le ne élément

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

Essayez-le en ligne!

Python 2 , 56 octets

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

Essayez-le en ligne!

Commenté

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

Essayez-le en ligne!

Gelée , 8 octets

P‘ÆfṂṭµ¡

Un programme complet (utilisant l'indexation zéro) acceptant $P_0$ et $n$ qui imprime une représentation Jelly de la liste des $P_0$ à $P_n$compris. (En tant que lien dyadique, avec n=0nous recevrons un entier, pas une liste.)

Essayez-le en ligne!

Comment?

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

05AB1E , 8 octets

GDˆ¯P>fß

La première entrée est $n$, le second est premier $p$.

Essayez-le en ligne ou bien d'autres cas de test (la suite de tests n'a pas les cas de test pour$n\geq9$, parce que pour $p=2$ et $p=5$la fonction intégrée fprend trop de temps).

Explication:

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)

Japt , 12 11 octets

Nous avons eu du mal à obtenir celui-ci, donc vous avez peut-être raté quelque chose qui peut être joué au golf.

Prend ncomme première entrée et p1, comme tableau singleton, comme seconde. Renvoie les premiers ntermes. Passez hà gpour renvoyer le nterme indexé à la place.

@Z×Ä k Î}hV

Essayez-le

@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

Rétine , 56 octets

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

\*
,

Essayez-le en ligne! Prend l'entrée comme le nombre de nouveaux termes à ajouter sur la première ligne et le ou les termes de départ sur la deuxième ligne. Remarque: devient très lent car il utilise la factorisation unaire, il doit donc créer une chaîne de la longueur appropriée. Explication:

,|$
$*

Remplacez les virgules dans les termes de départ par *s et ajoutez a *. Cela crée une expression Retina pour une chaîne de longueur du produit des valeurs.

"$&"{
)`

Répétez la boucle le nombre de fois donné par la première entrée.

~`.+¶
$$¶_

Remplacez temporairement le nombre sur la première ligne par un $et ajoutez a _à la deuxième ligne, puis évaluez le résultat en tant que programme Retina, ajoutant ainsi une chaîne de _s de longueur 1 de plus que le produit des valeurs.

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

Trouvez le plus petit facteur non trivial du nombre en décimal et ajoutez un *prêt pour la prochaine boucle.

1A`

Supprimez l'entrée d'itération.

.$

Supprimez le dernier *.

\*
,

Remplacez les *s restants par ,s.

JavaScript (Node.js) , 54 octets

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

Essayez-le en ligne!

Non 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

bash + GNU coreutils, 89 octets

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

TIO

Ruby 2.6, 51 octets

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

(2..), la plage infinie à partir de 2, n'est pas encore prise en charge sur TIO.

Il s'agit d'une fonction récursive qui prend une valeur de départ s(peut être un nombre premier ou composite), la renvoie lorsque n = 0 (modifier: notez que cela signifie qu'elle est indexée zéro), renvoie le plus petit nombre lsupérieur à 1 et se divise -(s+1)lorsque n = 1, et sinon revient avec s=l*set n=n-1.

APL (Dyalog Extended) , 15 octets

Ceci est une mise en œuvre assez simple de l'algorithme qui utilise de très étendus facteurs premiers utiles builtin, ⍭. Essayez-le en ligne!

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

Explication

{⍵,⊃⍭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.

Pari / GP , 47 octets

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

Essayez-le en ligne!

Stax , 9 octets

é|G╝╓c£¼_

Exécuter et déboguer

Prend et (indexé zéro) pour l'entrée. Produit .p0npn

C (gcc) , 54 53 octets

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

Essayez-le en ligne!

-1 octet grâce au plafond

Perl 6 , 33 32 octets

-1 octet grâce à nwellnhof

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

Essayez-le en ligne!

Bloc de code anonyme qui prend un nombre et renvoie une liste paresseuse.

Explication:

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

Haskell , 49 octets

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

Essayez-le en ligne!

Renvoie la séquence infinie sous forme de liste paresseuse.

Explication:

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