Une infinité de nombres premiers

26

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 p1,p2,...,pn , alors sûrement m:=p1p2...pn+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 23+1=7 , puis 237+1=43 , puis 23743+1=13139 , donc et13139sont 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 p1 et un nombre entier n calculer le n -ième terme pn de la séquence définie comme suit:

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

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

Exemples

Pour p1=2 :

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

Pour p1=5 ( A051308 ):

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

Pour p1=97 ( A051330 )

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

Réponses:

10

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
Arnauld
la source
9

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é p1 et n , le programme fait ce qui suit:

  • Commence par p1 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 [λ0,λ1,λ2,,λn1] ), où n représente le numéro d'itération actuel.
  • Le reste est trivial: Pprend le produit ( λ0λ1λ2λn-1 ), en >ajoute un à ce produit et fWrécupère le facteur premier minimum.
M. Xcoder
la source
6

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!

Galen Ivanov
la source
1
(,0({q:)1+*/)^:pendant 15 octets, retour de la séquence jusqu'à n(indexé zéro)
miles
@miles Merci!
Galen Ivanov
Très agréable. @miles que se passe-t-il exactement grammaticalement? nous mettons un verbe et une conjonction ensemble et récupérons un verbe dyadique. Je pensais avoir verb conj produit un adverbe .
Jonah
1
@Jonah, c'est un truc que j'ai appris en jouant au golf. Je pense que c'est l'une des anciennes règles d'analyse qui est toujours valide
miles
@miles Je viens de réaliser que c'est un adverbe (ou adnoun). Il modifie le nom à sa gauche, qui "s'attache" à la droite de la ^:, puis cela devient un verbe qui s'applique à l'argument de droite. Je pense que c'est ce qui se passe grammaticalement.
Jonah
5

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!

ovs
la source
Je viens de commencer avec Python, mais avez - vous besoin int(input())autrement iest str?
Anthony
2
En Python 3, cela serait vrai car input()renvoie toujours des chaînes. En Python 2 input()essaie d'évaluer l'entrée. J'utilise Python 2 dans ce cas car le code résultant est légèrement plus court. Pour le vrai code, vous devriez essayer d'utiliser Python 3 car c'est la version la plus récente et la plus prise en charge de Python.
OVS
Comment cela se termine-t-il après n étapes?
sintax
@sintax, il génère la séquence pour un p1 donné indéfiniment, comme le permettent les règles de séquence par défaut .
OVS
4

Gelée , 8 octets

P‘ÆfṂṭµ¡

Un programme complet (utilisant l'indexation zéro) acceptant P0 et n qui imprime une représentation Jelly de la liste des P0 à Pncompris. (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
Jonathan Allan
la source
3

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 pourn9, parce que pour p=2 et p=5la 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)
Kevin Cruijssen
la source
J'avais λλP>fW(6 octets) avec sortie sous forme de liste infinie et λ£λP>fW(7 octets) pour le premierntermes. Cependant, obtenir lenedevrait être de 9 octets ... Si seulement nous avions un drapeau comme £mais pour le dernier élément!
M. Xcoder
@ Mr.Xcoder " Si seulement nous avions un drapeau comme £mais pour le dernier élément! ", Comme ? ;) EDIT: En fait, cela ne fonctionne pas exactement comme £pour les listes .. en utilisant une liste comme [1,2]avec des résultats dans deux éléments en vrac avec les 1 et 2 derniers éléments (c'est-à-dire 12345devient à la [5,45]place de [45,3]ou [3,45], avec 12S.£) ..
Kevin Cruijssen
Umm, non, je ne vois pas comment ça λ.£devrait marcher. J'ai utilisé le drapeau comme dans une fonction supplémentaire associée à λ(voir cette conversation avec Adnan ). Je veux essentiellement un indicateur ètel que lors de son exécution, λè...}il générerait le n-ième élément plutôt que le flux infini (tout comme λ£pour la génération des n premiers éléments).
M. Xcoder
@ Mr.Xcoder Ah désolé, vous avez utilisé £pour l'environnement récursif. Ouais, alors λ.£ça ne marchera pas, mon mauvais. Nice 6 octets malgré tout. Il ne vous reste plus qu'à attendre la réponse de @flawr , qu'elle soit autorisée ou non (c'est probablement le cas).
Kevin Cruijssen
3

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
Hirsute
la source
3

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.

Neil
la source
2

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
Herman L
la source
2

bash + GNU coreutils, 89 octets

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

TIO

Nahuel Fouilleul
la source
2

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.

histocrate
la source
1
Vous devriez probablement mentionner que vous faites un indexage nul; J'ai remplacé (2..)par 2.step(juste 1 octet de plus) pour lui permettre de fonctionner sur TIO et tout était éteint par un. Essayez-le en ligne!
Value Ink
2

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.
Sherlock9
la source
1

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
Jo King
la source
1
-+^[*](@_)enregistre un octet.
nwellnhof
0

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
Jo King
la source