Sejak Euclid, kita tahu bahwa ada banyak bilangan prima yang tak terhingga. Argumennya berdasarkan kontradiksi: Jika hanya ada banyak, katakan saja , maka pasti tidak dapat dibagi oleh salah satu dari bilangan prima ini, sehingga faktorisasi prima harus menghasilkan perdana baru yang tidak ada dalam daftar. Jadi anggapan bahwa hanya bilangan prima yang ada ada adalah salah. $p_1,p_2,...,p_n$ $m:=p_1\cdot p_2\cdot...\cdot p_n+1$

Sekarang mari kita asumsikan adalah satu-satunya yang utama Metode dari hasil di atas sebagai prime baru (mungkin). Menerapkan metode ini sekali lagi menghasilkan , dan kemudian , lalu , jadi keduanya dan adalah bilangan prima baru, dll. Dalam kasus di mana kita mendapatkan nomor gabungan, kita hanya mengambil bilangan prima paling baru. Ini menghasilkan 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$

Tantangan

Diberikan utama dan bilangan bulat menghitung istilah ke- dari urutan yang didefinisikan sebagai berikut: $p_1$ $n$ $n$ $p_n$

p_{n} := min (primefactors (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))$

Urutan-urutan ini dikenal sebagai urutan -Euclid-Mullin .

Contohnya

Untuk $p_1 = 2$ :

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

Untuk $p_1 = 5$ ( A051308 ):

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

Untuk $p_1 = 97$ ( A051330 )

code-golf sequence integer primes factoring cacat
sumber

10

JavaScript (ES6), 45 44 byte

Mengambil input sebagai (n)(p1), di mana diindeks 0. $n$

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

Cobalah online!

Berkomentar

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
sumber

9

05AB1E , 6 byte

Ini menghasilkan dan aliran keluaran tanpa batas.

λλP>fW

Cobalah online! (tautan menyertakan versi yang sedikit dimodifikasi λ£λP>fW,, yang sebagai gantinya menghasilkan istilah pertama ) $n$

Penjelasan

Sangat mudah. Diberikan dan , program melakukan hal berikut: $p_1$ $n$

Mulai dengan sebagai parameter awal untuk aliran tak terbatas (yang dihasilkan menggunakan yang pertama ) dan memulai lingkungan rekursif yang menghasilkan istilah baru setelah setiap interaksi dan menambahkannya ke aliran. $p_1$ λ
Yang kedua λ, sekarang digunakan di dalam lingkungan rekursif, mengubah fungsinya: Sekarang, ia mengambil semua elemen yang dihasilkan sebelumnya (yaitu daftar ), di mana merupakan nomor iterasi saat ini. $[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]$ $n$
Sisanya sepele: Pmengambil produk ( ), menambahkan satu ke produk ini, dan mengambil faktor prima minimum minimum. $\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}$ >fW

Tuan Xcoder
sumber

6

J , 15 byte

-10 byte terima kasih untuk miles!

Mengembalikan urutan hingga n (diindeks-nol) - terima kasih kepada @miles

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

Cobalah online!

J , 25 byte

Mengembalikan nitem th

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

Cobalah online!

Galen Ivanov
sumber

1

(,0({q:)1+*/)^:selama 15 byte, mengembalikan urutan hingga n(diindeks-nol)

mil

@miles, terima kasih!

Galen Ivanov

Sangat bagus. @miles apa sebenarnya yang terjadi di sana secara tata bahasa? kita menempatkan kata kerja dan kata kerja bersama dan mendapatkan kata kerja diad kembali. Saya pikir verb conj menghasilkan kata keterangan .

Jonah

1

@Jonah itu tipuan yang saya pelajari dari bermain golf. Saya pikir itu salah satu aturan penguraian yang lebih lama yang masih berlaku

mil

@miles Saya baru sadar itu kata keterangan (atau adnoun). Ini memodifikasi kata benda ke kiri, yang "menempel" di sebelah kanan ^:, dan kemudian itu menjadi kata kerja yang berlaku untuk arg kanan. Saya pikir itulah yang terjadi secara tata bahasa.

Jonah

5

Python 2 , 56 byte

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

Cobalah online!

Berkomentar

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

Cobalah online!

ovs
sumber

Aku baru saja mulai dengan Python, tetapi apakah Anda membutuhkan int(input())sebaliknya iadalah str?

Anthony

2

Dalam Python 3 ini akan benar karena input()selalu mengembalikan string. Dalam Python 2 input()mencoba untuk mengevaluasi input. Saya menggunakan Python 2 dalam hal ini karena kode yang dihasilkan sedikit lebih pendek. Untuk kode nyata Anda harus mencoba menggunakan Python 3 karena ini adalah versi Python yang lebih baru dan lebih didukung.

Ovs

Bagaimana ini berakhir setelah n langkah?

sintax

@sintax itu mengeluarkan urutan untuk p1 yang diberikan tanpa batas, sebagaimana diizinkan oleh aturan urutan default .

Ovs

4

Jelly , 8 byte

P‘ÆfṂṭµ¡

Program lengkap (menggunakan pengindeksan nol) menerima dan yang mencetak representasi Jelly dari daftar hingga inklusif. (Sebagai Tautan diadik, dengan kami akan diberikan kembali bilangan bulat, bukan daftar.) $P_0$ $n$ $P_0$ $P_n$ n=0

Cobalah online!

Bagaimana?

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
sumber

3

05AB1E , 8 byte

GDˆ¯P>fß

Input pertama adalah , kedua adalah prime . $n$ $p$

Cobalah secara online atau beberapa test case lagi (test suite tidak memiliki case test untuk , karena untuk dan builtin $n\geq9$ $p=2$ $p=5$ f membutuhkan waktu terlalu lama).

Penjelasan:

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
sumber

Saya punya λλP>fW(6 byte) dengan output sebagai daftar tak terbatas dan λ£λP>fW(7 byte) untuk istilah pertama . Namun mendapatkan harus 9 byte ... Kalau saja kita memiliki flag seperti tetapi untuk elemen terakhir!

n

$n$

n^{th}

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

Tn. Xcoder

@ Mr.Xcoder " Kalau saja kita memiliki bendera seperti £tetapi untuk elemen terakhir! ", Seperti .£? ;) EDIT: Sebenarnya, itu tidak bekerja persis seperti £untuk daftar .. menggunakan daftar suka [1,2]dengan .£hasil dalam dua item longgar dengan 1 dan 2 item terakhir (yaitu 12345menjadi [5,45]bukan [45,3]atau [3,45], dengan 12S.£) ..

Kevin Cruijssen

Umm, tidak, aku tidak mengerti bagaimana cara λ.£kerjanya. Saya menggunakan bendera sebagai fungsi tambahan yang terkait λ(lihat percakapan ini dengan Adnan ). Saya pada dasarnya menginginkan beberapa flag èsehingga ketika dijalankan λè...}akan menghasilkan elemen ke-n daripada aliran tanpa batas (sama seperti λ£bekerja untuk menghasilkan elemen n pertama).

Tn. Xcoder

@ Mr.Xcoder Ah maaf, Anda telah menggunakan £untuk lingkungan rekursif. Ya, maka λ.£memang tidak akan berhasil, salahku. Nice 6-byter bagaimanapun. Sekarang Anda hanya perlu menunggu jawaban @ flawr apakah diizinkan atau tidak (mungkin).

Kevin Cruijssen

3

Japt , 12 11 byte

Berjuang untuk mendapatkan yang ini benar sehingga mungkin telah melewatkan sesuatu yang bisa bermain golf.

Dibawa nsebagai input pertama dan p1, sebagai array tunggal, sebagai input kedua. Mengembalikan nsyarat pertama . Ubah huntuk gmengembalikan istilah n0-diindeks sebagai gantinya.

@Z×Ä k Î}hV

Cobalah

@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

Shaggy
sumber

3

Retina , 56 byte

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

\*
,

Cobalah online! Mengambil input sebagai jumlah istilah baru untuk ditambahkan pada baris pertama dan istilah seed pada baris kedua. Catatan: Mendapat sangat lambat karena menggunakan factorisation unary sehingga perlu membuat string dengan panjang yang relevan. Penjelasan:

,|$
$*

Ganti koma dalam ketentuan seed dengan *s dan tambahkan a *. Ini menciptakan ekspresi Retina untuk serangkaian panjang produk nilai.

"$&"{
)`

Ulangi loop berapa kali yang diberikan oleh input pertama.

~`.+¶
$$¶_

Ganti sementara angka pada baris pertama dengan a $dan tambahkan a _ke baris kedua, kemudian evaluasi hasilnya sebagai program Retina, sehingga menambahkan string _dengan panjang 1 lebih dari produk nilai.

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

Temukan faktor nontrivial terkecil dari angka dalam desimal dan tambahkan tanda *siap untuk loop berikutnya.

1A`

Hapus input iterasi.

.$

Hapus yang terakhir *.

\*
,

Ganti sisanya *dengan ,s.

Neil
sumber

2

JavaScript (Node.js) , 54 byte

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

Cobalah online!

Tidak disatukan

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.
sumber

2

bash + GNU coreutils, 89 byte

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

TIO

Nahuel Fouilleul
sumber

2

Ruby 2.6, 51 byte

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

(2..), rentang tak terbatas mulai dari 2, belum didukung di TIO.

Ini adalah fungsi rekursif yang mengambil nilai awal s(dapat berupa prime atau komposit), mengembalikannya ketika n = 0 (edit: perhatikan bahwa ini berarti diindeks nol), mengembalikan angka paling kecil lyang lebih besar dari 1 dan membaginya -(s+1)saat n = 1, dan jika tidak berulang dengan s=l*sdan n=n-1.

histokrat
sumber

1

Anda mungkin harus menyebutkan bahwa Anda melakukan indeks-nol; Saya diganti (2..)dengan 2.step(hanya 1 byte lebih lama) untuk memungkinkannya untuk bekerja pada TIO dan semuanya dimatikan satu per satu. Cobalah online!

Nilai Tinta

2

APL (Dyalog Extended) , 15 byte

Ini adalah implementasi yang cukup sederhana dari algoritma yang menggunakan faktor prima Extended yang sangat membantu ⍭. Cobalah online!

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

Penjelasan

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

1

Pari / GP , 47 byte

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

Cobalah online!

alephalpha
sumber

1

Stax , 9 byte

é|G╝╓c£¼_

Jalankan dan debug itu

Mengambil dan (diindeks nol) untuk input. Menghasilkan .p₀np_n

rekursif
sumber

1

C (gcc) , 54 53 byte

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

Cobalah online!

-1 byte berkat ceilingcat

wastl
sumber

1

Perl 6 , 33 32 byte

-1 byte terima kasih kepada nwellnhof

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

Cobalah online!

Blok kode anonim yang mengambil nomor dan mengembalikan daftar malas.

Penjelasan:

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

1

-+^[*](@_)menghemat satu byte.

nwellnhof

0

Haskell , 49 byte

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

Cobalah online!

Mengembalikan urutan tak terbatas sebagai daftar malas.

Penjelasan:

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
sumber

Tak terhingga banyaknya bilangan prima

Tantangan

Contohnya

Jawaban:

JavaScript (ES6), 45 44 byte

Berkomentar

05AB1E , 6 byte

Penjelasan

J , 15 byte

J , 25 byte

Python 2 , 56 byte

Berkomentar

Jelly , 8 byte

Bagaimana?

05AB1E , 8 byte

Japt , 12 11 byte

Retina , 56 byte

JavaScript (Node.js) , 54 byte

bash + GNU coreutils, 89 byte

Ruby 2.6, 51 byte

APL (Dyalog Extended) , 15 byte

Pari / GP , 47 byte

Stax , 9 byte

C (gcc) , 54 53 byte

Perl 6 , 33 32 byte

Penjelasan:

Haskell , 49 byte

Penjelasan: