Unendlich viele Primzahlen

26

Seit Euklid wissen wir, dass es unendlich viele Primzahlen gibt. Das Argument ist widersprüchlich: Wenn es nur endlich viele gibt, sagen wir , dann ist durch keines von teilbar Diese Primzahlen, also muss ihre Primfaktorisierung eine neue Primzahl ergeben, die nicht in der Liste enthalten war. Die Annahme, dass nur endlich Primzahlen existieren, ist also falsch.p1,p2,...,pnm:=p1p2...pn+1

Nehmen wir nun an, dass die einzige Primzahl ist. Die obige Methode ergibt als neue (mögliche) Primzahl. Die erneute Anwendung der Methode ergibt und dann , dann , also beide und sind neue Primzahlen usw. Wenn wir eine zusammengesetzte Zahl erhalten, nehmen wir nur die am wenigsten neue Primzahl. Dies führt zu A000945 .22+1=323+1=7237+1=4323743+1=1313913139

Herausforderung

Berechnen Sie bei gegebener Primzahl und einer ganzen Zahl den ten Term der Sequenz, die wie folgt definiert ist:p1nnpn

pn:=min(primefactors(p1p2...pn1+1))

Diese Sequenzen sind als Euklid-Mullin- Sequenzen bekannt.

Beispiele

Für :p1=2

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

Für ( A051308 ):p1=5

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

Für ( A051330 )p1=97

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

Antworten:

10

JavaScript (ES6),  45  44 Bytes

Nimmt die Eingabe als an (n)(p1), wobei n mit 0 indiziert ist.

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

Probieren Sie es online!

Kommentiert

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
quelle
9

05AB1E , 6 Bytes

Dies erzeugt einen unendlichen Ausgangsstrom.

λλP>fW

Probieren Sie es online! (Link enthält eine leicht modifizierte Version λ£λP>fW, die stattdessen die ersten n Terme ausgibt )

Erläuterung

Sehr einfach. Wenn p1 und n , führt das Programm Folgendes aus:

  • Beginnt mit p1 als Anfangsparameter für den unendlichen Stream (der mit dem ersten generiert wird λ) und beginnt eine rekursive Umgebung, die nach jeder Interaktion einen neuen Term generiert und an den Stream anfügt.
  • Das zweite Element λ, das jetzt in der rekursiven Umgebung verwendet wird, ändert seine Funktionalität: Jetzt werden alle zuvor generierten Elemente (dh die Liste [λ0,λ1,λ2,,λn-1] ) abgerufen , wobei n für das steht aktuelle Iterationsnummer.
  • Der Rest ist trivial: PNimmt das Produkt ( λ0λ1λ2λn-1 ), >addiert eins zu diesem Produkt und ermittelt fWden minimalen Primfaktor.
Mr. Xcoder
quelle
6

J , 15 Bytes

-10 Bytes dank Meilen!

Rückgabe der Sequenz bis n (null-indiziert) - dank @miles

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

Probieren Sie es online!

J , 25 Bytes

Gibt den nth-Artikel zurück

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

Probieren Sie es online!

Galen Ivanov
quelle
1
(,0({q:)1+*/)^:Für 15 Byte wird die Sequenz zurückgegeben bis n(null-indiziert)
Meilen,
@miles Danke!
Galen Ivanov
Sehr schön. @miles was genau passiert da grammatikalisch? Wir setzen ein Verb und eine Konjunktion zusammen und erhalten ein dyadisches Verb zurück. Ich dachte verb conj produziert ein Adverb .
Jonah,
1
@Jonah, das ist ein Trick, den ich beim Golfen gelernt habe. Ich denke, es ist eine der älteren Parsing-Regeln, die noch gültig ist
Meilen
@miles Mir ist gerade aufgefallen, dass es sich um ein Adverb (oder Adnomen) handelt. Es modifiziert das Nomen zu seiner Linken, das rechts von dem "anhängt" ^:, und das wird dann zu einem Verb, das für das rechte Argument gilt. Ich denke, das passiert grammatikalisch.
Jonah
5

Python 2 , 56 Bytes

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

Probieren Sie es online!


Kommentiert

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

Probieren Sie es online!

ovs
quelle
Ich habe gerade mit Python angefangen, aber brauchst du int(input())sonst inoch eine str?
Anthony
2
In Python 3 wäre dies der Fall, da input()immer Zeichenfolgen zurückgegeben werden. In Python 2 wird input()versucht, die Eingabe auszuwerten. In diesem Fall verwende ich Python 2, da der resultierende Code etwas kürzer ist. Für echten Code sollten Sie versuchen, Python 3 zu verwenden, da es die neuere und unterstütztere Version von Python ist.
ovs
Wie endet dies nach n Schritten?
Sintax
@sintax gibt die Sequenz für einen bestimmten p1 auf unbestimmte Zeit aus, wie dies nach den Standardsequenzregeln zulässig ist .
Ovs
4

Gelee , 8 Bytes

P‘ÆfṂṭµ¡

P0nP0Pnn=0

Probieren Sie es online!

Wie?

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
quelle
3

05AB1E , 8 Bytes

GDˆ¯P>fß

np

n9p=2p=5f

Erläuterung:

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
quelle
λλP>fWλ£λP>fWnnth£
@ Mr.Xcoder " Wenn wir nur eine Fahne hätten, £aber für das letzte Element! ", Wie ? ;) BEARBEITEN: Eigentlich funktioniert es nicht genau wie £bei Listen. Verwenden einer Liste [1,2]mit Ergebnissen in zwei losen Elementen mit den letzten 1 und 2 Elementen (dh 12345wird [5,45]anstelle von [45,3]oder [3,45]mit 12S.£).
Kevin Cruijssen
Ähm, nein, ich sehe nicht, wie λ.£das funktionieren soll. Ich habe flag als zusätzliche Funktion verwendet λ(siehe dieses Gespräch mit Adnan ). Grundsätzlich möchte ich ein Flag è, das beim Ausführen λè...}das n-te Element und nicht den unendlichen Stream generiert (genau wie λ£beim Generieren der ersten n Elemente).
Mr. Xcoder
@ Mr.Xcoder Ah sorry, du hast das £für die rekursive Umgebung benutzt. Ja, dann λ.£wird es ja nicht klappen, mein Schlimmes. Trotzdem netter 6-Byter. Jetzt musst du nur noch auf die Antwort von @flawr warten , ob es erlaubt ist oder nicht (es ist wahrscheinlich).
Kevin Cruijssen
3

Japt , 12 11 Bytes

Mühte sich ab, dies zu korrigieren, so dass möglicherweise etwas verpasst wurde, das golfen werden kann.

Nimmt nals erste Eingabe und p1als Singleton-Array als zweite. Gibt die ersten nTerme zurück. Wechseln Sie hzu g, um nstattdessen den th 0-indizierten Begriff zurückzugeben.

@Z×Ä k Î}hV

Versuch es

@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
Zottelig
quelle
3

Netzhaut , 56 Bytes

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

\*
,

Probieren Sie es online! Nimmt die Eingabe als die Anzahl der neuen Terme, die in der ersten Zeile hinzugefügt werden sollen, und die Startterme in der zweiten Zeile. Hinweis: Wird sehr langsam, da die unäre Faktorisierung verwendet wird und daher eine Zeichenfolge mit der entsprechenden Länge erstellt werden muss. Erläuterung:

,|$
$*

Ersetzen Sie die Kommas in den Startwerten durch *s und fügen Sie a hinzu *. Dadurch wird ein Retina-Ausdruck für eine Zeichenfolge der Länge des Produkts der Werte erstellt.

"$&"{
)`

Wiederholen Sie die Schleife so oft, wie sie von der ersten Eingabe angegeben wurde.

~`.+¶
$$¶_

Ersetzen Sie die Zahl in der ersten Zeile vorübergehend durch a $und stellen Sie a _vor die zweite Zeile, und werten Sie das Ergebnis als Retina-Programm aus. Fügen Sie dabei eine Zeichenfolge _der Länge 1 hinzu, die größer ist als das Produkt der Werte.

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

Finden Sie den kleinsten nichttrivialen Faktor der Zahl in Dezimalzahl und hängen Sie ein *Ready für die nächste Schleife an.

1A`

Löschen Sie die Iterationseingabe.

.$

Löschen Sie den letzten *.

\*
,

Ersetzen Sie das verbleibende *s durch ,s.

Neil
quelle
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

Probieren Sie es online!

Ungolfed

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
quelle
2

Bash + GNU Coreutils, 89 Bytes

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

TIO

Nahuel Fouilleul
quelle
2

Ruby 2.6, 51 Bytes

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

(2..), der unendliche Bereich ab 2, wird von TIO noch nicht unterstützt.

Dies ist eine rekursive Funktion, die einen Startwert annimmt s(kann eine Primzahl oder eine Zusammensetzung sein), ihn zurückgibt, wenn n = 0 ist (Bearbeiten: Beachten Sie, dass dies bedeutet, dass er mit Null indexiert ist), die kleinste Zahl zurückgibt l, die größer als 1 ist, und -(s+1)wenn n dividiert = 1 und ansonsten rekursiv mit s=l*sund n=n-1.

Histokrat
quelle
1
Sie sollten wahrscheinlich erwähnen, dass Sie mit einem Index von Null arbeiten. Ich ersetzen (2..)mit 2.step(nur 1 Byte länger), um die Arbeit an TIO zu ermöglichen und alles war weg nach der anderen. Probieren Sie es online!
Value Ink
2

APL (Dyalog Extended) , 15 Byte

Dies ist eine ziemlich einfache Implementierung des Algorithmus, der die sehr hilfreichen Primfaktoren von Extended verwendet . Probieren Sie es online!

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

Erläuterung

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

Perl 6 , 33 32 Bytes

-1 byte dank nwellnhof

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

Probieren Sie es online!

Anonymer Codeblock, der eine Nummer entgegennimmt und eine Lazy List zurückgibt.

Erläuterung:

{                              }  # 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
Scherzen
quelle
1
-+^[*](@_)Speichert ein 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)

Probieren Sie es online!

Gibt die unendliche Folge als Lazy List zurück.

Erläuterung:

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
Scherzen
quelle