Od Euklidesa wiemy, że istnieje nieskończenie wiele liczb pierwszych. Argument jest sprzeczność: Jeśli istnieje tylko skończenie wiele, powiedzmy $p_1,p_2,...,p_n$ , a następnie na pewno $m:=p_1\cdot p_2\cdot...\cdot p_n+1$ nie jest podzielne przez żadną z tych liczb pierwszych, więc jego rozkład na czynniki pierwsze musi dać nową liczbę pierwszą, której nie było na liście. Zatem założenie, że istnieją tylko skończone liczby pierwsze, jest fałszywe.

Załóżmy teraz, że $2$ jest jedyną liczbą pierwszą. Powyższa metoda daje $2+1=3$ jako nową (możliwą) liczbę pierwszą. Ponowne zastosowanie metody daje $2\cdot 3+1=7$ , a następnie $2\cdot 3\cdot 7+1=43$ , a następnie $2\cdot 3\cdot 7\cdot 43+1=13\cdot 139$ , więc zarówno $13$ jak i $139$są nowe liczby pierwsze itp. W przypadku, gdy otrzymujemy liczbę całkowitą, bierzemy najmniejszą liczbę pierwszą. Daje to wynik A000945 .

Wyzwanie

Biorąc pod uwagę liczbę pierwszą $p_1$ i liczbę całkowitą $n$ oblicz $n$ ty składnik $p_n$ sekwencji zdefiniowanej w następujący sposób:

Sekwencje te są znane jako Euclid-Mullin .

Przykłady

Dla :$p_1 = 2$

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

Dla ( A051308 ):$p_1 = 5$

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

Dla ( A051330 )$p_1 = 97$

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

JavaScript (ES6),  45  44 bajtów

Pobiera dane wejściowe jako (n)(p1), gdzie $n$ jest indeksowane jako 0.

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

Wypróbuj online!

Skomentował

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 bajtów

Daje to nieskończony strumień wyjściowy.

λλP>fW

Wypróbuj online! (link zawiera nieco zmodyfikowaną wersję λ£λP>fW, która zamiast tego wyświetla pierwsze $n$ warunków)

Wyjaśnienie

Bardzo proste. Biorąc pod uwagę $p_1$ i $n$ , program wykonuje następujące czynności:

• Zaczyna się od $p_1$ jako parametru początkowego dla nieskończonego strumienia (który jest generowany przy użyciu pierwszego λ) i rozpoczyna środowisko rekurencyjne które generuje nowy termin po każdej interakcji i dołącza go do strumienia.
• Drugi λ, obecnie używany w środowisku rekurencyjnym, zmienia swoją funkcjonalność: Teraz pobiera wszystkie wcześniej wygenerowane elementy (tj. Listę $[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]$ ), gdzie $n$ oznacza aktualny numer iteracji.
• Reszta jest trywialna: Pbierze iloczyn ( $\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}$ ), >dodaje jeden do tego produktu i fWpobiera minimalny współczynnik pierwszy.

J , 15 bajtów

-10 bajtów dzięki milom!

Zwracanie sekwencji do n (indeksowane od zera) - dzięki @miles

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

Wypróbuj online!

J , 25 bajtów

Zwraca nth rzecz

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

Wypróbuj online!

Python 2 , 56 bajtów

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

Wypróbuj online!

Skomentował

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

Wypróbuj online!

Galaretka , 8 bajtów

P‘ÆfṂṭµ¡

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

Wypróbuj online!

W jaki sposób?

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 bajtów

GDˆ¯P>fß

$n$$p$

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

Wyjaśnienie:

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 bajtów

Walczyłem o to, aby być w stanie dobrze, więc mogłem przegapić coś, co można zagrać w golfa.

Pobiera njako pierwsze wejście, a p1jako tablica singletonów jako drugie. Zwraca pierwsze nwarunki. Zmień, haby zamiast tego gzwrócić nth indeksowany indeks 0.

@Z×Ä k Î}hV

Spróbuj

@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

Siatkówka , 56 bajtów

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

\*
,

Wypróbuj online! Pobiera dane wejściowe jako liczbę nowych terminów do dodania w pierwszym wierszu i termin (y) początkowy w drugim wierszu. Uwaga: Staje się bardzo wolny, ponieważ wykorzystuje jednoargumentowe dzielenie, więc musi utworzyć ciąg o odpowiedniej długości. Wyjaśnienie:

,|$
$*

Zamień przecinki w terminach *początkowych na s i dodaj *. To tworzy wyrażenie Retina dla ciągu długości iloczynu wartości.

"$&"{
)`

Powtórz pętlę tyle razy, ile podało pierwsze wejście.

~`.+¶
$$¶_

Tymczasowo zamień liczbę w pierwszym wierszu na a $i wstaw znak a _do drugiego wiersza, a następnie oceń wynik jako program Retina, dodając w ten sposób ciąg _s długości 1 więcej niż iloczyn wartości.

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

Znajdź najmniejszy nietrywialny współczynnik liczby dziesiętnej i dołącz *gotową do następnej pętli.

1A`

Usuń wejście iteracji.

.$

Usuń ostatni *.

\*
,

Zamień pozostałe *s na ,s.

JavaScript (Node.js) , 54 bajty

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

Wypróbuj online!

Nie golfił

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 bajtów

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

TIO

Ruby 2.6, 51 bajtów

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

(2..), nieskończony zakres od 2, nie jest jeszcze obsługiwany w TIO.

Jest to funkcja rekurencyjna, która przyjmuje wartość początkową s(może być liczbą pierwszą lub złożoną), zwraca ją, gdy n = 0 (edytuj: zauważ, że oznacza to, że ma indeks zerowy), zwraca najmniejszą liczbę lwiększą niż 1 i dzieli, -(s+1)gdy n = 1, a w przeciwnym razie powtarza się za pomocą s=l*si n=n-1.

APL (Dyalog Extended) , 15 bajtów

Jest to dość prosta implementacja algorytmu, który używa rozszerzeń bardzo pomocne czynniki prime wbudowane, ⍭. Wypróbuj online!

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

Wyjaśnienie

{⍵,⊃⍭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 bajtów

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

Wypróbuj online!

Stax , 9 bajtów

é|G╝╓c£¼_

Uruchom i debuguj

Pobiera i (indeksowane od zera) do wprowadzenia. Produkuje .p0npn

C (gcc) , 54 53 bajtów

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

Wypróbuj online!

-1 bajt dzięki pułapkowi cat

Perl 6 , 33 32 bajty

-1 bajt dzięki nwellnhof

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

Wypróbuj online!

Anonimowy blok kodu, który pobiera liczbę i zwraca leniwą listę.

Wyjaśnienie:

{                              }  # 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 bajtów

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

Wypróbuj online!

Zwraca nieskończoną sekwencję jako leniwą listę.

Wyjaśnienie:

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