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:

p_{n} : = min (czynniki pierwsze (p_{1} \cdot p_{2)} \cdot . . . \cdot p_{n - 1} + 1))

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

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$

— wada
źródło

10

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

— Arnauld
źródło

9

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.

— Pan Xcoder
źródło

6

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!

— Galen Iwanow
źródło

1

(,0({q:)1+*/)^:przez 15 bajtów, zwracając sekwencję do n(indeksowane od zera)

— mile

@miles Dziękujemy!

— Galen Iwanow

Bardzo dobrze. @miles, co dokładnie się tam dzieje gramatycznie? łączymy czasownik i koniunkcję razem i otrzymujemy zwrotnik czasownikowy. Myślałem, że verb conj wyprodukowałem przysłówek .

— Jonasz

1

@Jonah to sztuczka, której nauczyłem się od gry w golfa. Myślę, że jest to jedna ze starszych zasad analizy składni, która jest nadal aktualna

— mile

@miles Właśnie zdałem sobie sprawę, że to przysłówek (lub adnoun). Modyfikuje rzeczownika do jej lewej stronie, który „przywiązuje” się po prawej stronie ^:, a następnie , że staje się czasownik, który odnosi się do prawej arg. Myślę, że to się dzieje gramatycznie.

— Jonasz

5

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!

— ovs
źródło

Właśnie zacząłem z Python, ale czy trzeba int(input())inaczej ijest str?

— Anthony

2

W Pythonie 3 byłoby to prawdą, ponieważ input()zawsze zwraca łańcuchy. W Python 2 input()próbuje ocenić dane wejściowe. W tym przypadku używam języka Python 2, ponieważ wynikowy kod jest nieco krótszy. W przypadku prawdziwego kodu powinieneś spróbować użyć Pythona 3, ponieważ jest to nowsza i bardziej obsługiwana wersja Pythona.

— ovs

Jak to się kończy po n krokach?

— sintax

@sintax generuje sekwencję dla danego p1 w nieskończoność, na co pozwalają domyślne reguły sekwencji .

— ows

4

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

— Jonathan Allan
źródło

3

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)

— Kevin Cruijssen
źródło

λλP>fWλ£λP>fW

n

$n$

n^{th}

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

@ Mr.Xcoder „ Gdybyśmy tylko mieli flagę jak £dla ostatniego elementu! ”, Na przykład .£? ;) EDYCJA: Właściwie to nie działa dokładnie tak jak w £przypadku list. Używanie listy jak [1,2]z .£wynikami daje dwa luźne elementy z ostatnimi 1 i 2 elementami (tj. 12345Staje się [5,45]zamiast [45,3]lub [3,45], z 12S.£) ..

— Kevin Cruijssen

Umm, nie, nie rozumiem, jak λ.£powinno działać. Użyłem flagi jak w dodatkowej funkcji związanej z λ(patrz rozmowa z Adnanem ). Zasadniczo chcę ètaką flagę , aby po uruchomieniu λè...}generowała n-ty element zamiast nieskończonego strumienia (podobnie jak λ£działałaby przy generowaniu pierwszych n elementów).

— Pan Xcoder,

@ Mr.Xcoder Ach, przepraszam, wykorzystałeś £środowisko rekurencyjne. Tak, λ.£to naprawdę nie zadziała, mój zły. Niezły 6-bajter niezależnie. Teraz musisz tylko poczekać na odpowiedź @flawr , czy jest to dozwolone, czy nie (prawdopodobnie tak jest).

— Kevin Cruijssen

3

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

— Kudłaty
źródło

3

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.

— Neil
źródło

2

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

— Herman L.
źródło

2

bash + GNU coreutils, 89 bajtów

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

TIO

— Nahuel Fouilleul
źródło

2

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.

— histocrat
źródło

1

Prawdopodobnie powinieneś wspomnieć, że robisz indeksowanie zerowe; Wymieniłem (2..)z 2.step(tylko 1 bajt dłużej), aby umożliwić jej do pracy na TIO i wszystko było się o jeden. Wypróbuj online!

— Wartość tuszu

2

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.

— Sherlock9
źródło

1

Pari / GP , 47 bajtów

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

Wypróbuj online!

— alephalpha
źródło

1

Stax , 9 bajtów

é|G╝╓c£¼_

Uruchom i debuguj

Pobiera i (indeksowane od zera) do wprowadzenia. Produkuje .p₀np_n

— rekurencyjny
źródło

1

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

— pustkowie
źródło

1

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

— Jo King
źródło

1

-+^[*](@_)zapisuje bajt.

— nwellnhof

0

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

— Jo King
źródło

Nieskończenie wiele liczb pierwszych

Wyzwanie

Przykłady

JavaScript (ES6), 45 44 bajtów

Skomentował

05AB1E , 6 bajtów

Wyjaśnienie

J , 15 bajtów

J , 25 bajtów

Python 2 , 56 bajtów

Skomentował

Galaretka , 8 bajtów

W jaki sposób?

05AB1E , 8 bajtów

Japt , 12 11 bajtów

Siatkówka , 56 bajtów

JavaScript (Node.js) , 54 bajty

bash + GNU coreutils, 89 bajtów

Ruby 2.6, 51 bajtów

APL (Dyalog Extended) , 15 bajtów

Pari / GP , 47 bajtów

Stax , 9 bajtów

C (gcc) , 54 53 bajtów

Perl 6 , 33 32 bajty

Wyjaśnienie:

Haskell , 49 bajtów

Wyjaśnienie: