Les nombres premiers ont toujours fasciné les gens. Il y a 2300 ans, Euclide a écrit dans ses "Éléments"

Un nombre premier est celui qui est mesuré par une seule unité.

ce qui signifie qu'un nombre premier n'est divisible que par 1(ou par lui-même).

Les gens ont toujours cherché des relations entre les nombres premiers et ont trouvé des trucs assez bizarres (comme dans "intéressants").

Par exemple, un nombre premier de Sophie Germain est un nombre premier ppour lequel il 2*p+1est également premier.

Un nombre premier sûr est un nombre premier ppour lequel il (p-1)/2est également premier, ce qui est exactement la condition arrière d'un nombre premier de Sophie Germain.

Celles-ci sont liées à ce que nous recherchons dans ce défi.

Une chaîne de Cunningham de type I est une série de nombres premiers, où chaque élément, sauf le dernier, est un nombre premier de Sophie Germain , et chaque élément, sauf le premier, est un nombre premier sûr . Le nombre d'éléments dans cette chaîne est appelé sa longueur .

Cela signifie que nous commençons par un nombre premier pet calculons q=2*p+1. Si qest aussi premier, nous avons une chaîne de Cunnigham de type I de longueur 2. Ensuite, nous testons 2*q+1et ainsi de suite, jusqu'à ce que le prochain nombre généré soit composite.

Les chaînes Cunningham de type II sont construites suivant presque le même principe, la seule différence étant que nous vérifions 2*p-1à chaque étape.

Les chaînes de Cunningham peuvent avoir une longueur de 1 , ce qui signifie que ni 2 * p + 1 ni 2 * p-1 ne sont premiers. Cela ne nous intéresse pas .

Quelques exemples de chaînes Cunningham

2démarre une chaîne de type I de longueur 5.

2, 5, 11, 23, 47

Le prochain nombre construit serait celui 95qui n'est pas premier.
Cela nous dit aussi que 5, 11, 23et 47ne commencez pas la chaîne de type I , parce qu'il aurait des éléments précédents.

2démarre également une chaîne de type II de longueur 3.

2, 3, 5

Ensuite 9, ce n'est pas le premier.

Essayons 11pour le type II (nous l'avons exclu du type I plus tôt).
Eh bien, ce 21serait le suivant, qui n'est pas premier, donc nous aurions la longueur 1 pour cette "chaîne", que nous ne comptons pas dans ce défi.

Défi

Écrivez un programme ou une fonction qui, étant donné un nombre nen entrée, écrit / renvoie le numéro de départ de la nième chaîne de Cunningham de type I ou II d' au moins 2 , suivi d'un espace, suivi du type de chaîne qu'il démarre ( I ou II ), suivi de deux points, suivi de la longueur de ce type de chaîne. Dans le cas où un amorçage démarre les deux types de chaînes (type I et type II), la chaîne de type I est comptée en premier.

Exemple: 2 I:5

Gardez à l'esprit que cela npeut faire partie d'une chaîne de n'importe quel type précédemment démarrée, auquel cas il ne doit pas être considéré comme un numéro de départ d'une chaîne de ce type.

Voyons comment cela commence

Nous commençons par 2. Puisque c'est le premier premier, nous pouvons être sûrs qu'il n'y a pas de chaîne commençant par un premier inférieur qui contient 2.
Le numéro suivant dans une chaîne de type I serait 2*2+1 == 5. 5est premier, nous avons donc déjà une chaîne d'au moins 2.
Nous comptons cela comme la première chaîne. Et le type II? Le numéro suivant serait 2*2-1 == 3. 3est premier, donc une chaîne d'au moins 2 pour le type II aussi.
Nous comptons cela comme la deuxième chaîne. Et nous avons fini 2.

Le premier prime est 3. Ici, nous devons vérifier si c'est dans une chaîne qu'un amorçage inférieur a commencé.
Vérifiez type I: (3-1)/2 == 1. 1n'est pas premier, donc 3 pourrait être un point de départ pour une chaîne de type I.
Vérifions cela. Le prochain serait 3*2+1 == 7. 7est premier, nous avons donc une chaîne de type I d'au moins 2. Nous comptons cela comme la troisième chaîne.
Maintenant, nous vérifions si 3apparaît dans une chaîne de type II qu'un amorçage inférieur a commencé. (3+1)/2 == 2. 2est premier, donc 3 ne peut pas être considéré comme un nombre de départ pour une chaîne de type II. Donc, ce n'est pas compté, même si le nombre suivant après 3dans cette chaîne, qui serait5, est premier. (Bien sûr, nous le savions déjà, et vous pouvez et devez bien sûr réfléchir à votre propre méthode pour effectuer ces vérifications.)

Et donc nous vérifions pour 5, 7, 11et ainsi de suite, comptage jusqu'à ce que nous trouvons la nième chaîne Cunningham d'au moins une longueur de 2.

Ensuite (ou peut-être un peu plus tôt ;)), nous devons déterminer la longueur complète de la chaîne que nous avons trouvée et imprimer le résultat dans le format mentionné précédemment.

Soit dit en passant: dans mes tests, je n'ai pas trouvé d'autre 2amorce qui a démarré les deux types de chaînes avec une longueur supérieure à 1.

Exemples d'entrées / sorties

Contribution

1

Production

2 I:5

Contribution

10

Production

79 II:3

Contribution

99

Production

2129 I:2

Les sorties pour les entrées 1..20

2 I: 5
2 II: 3
3 I: 2
7 II: 2
19 II: 3
29 I: 2
31 II: 2
41 I: 3
53 I: 2
79 II: 3
89 I: 6
97 II: 2
113 I: 2
131 I: 2
139 II: 2
173 I: 2
191 I: 2
199 II: 2
211 II: 2
229 II: 2

Une liste des 5000 premières sorties peut être trouvée ici .

C'est le golf de code. Des espaces blancs arbitraires sont autorisés dans la sortie, mais le type et les nombres doivent être séparés par un seul espace et deux points comme indiqué dans les exemples. L'utilisation de failles n'est pas autorisée, en particulier l'obtention des résultats sur le Web n'est pas autorisée.

Bonne chance :)

Javascript, 236 208 octets

28 octets enregistrés:

p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

9 octets enregistrés sur la pfonction avec: p=(n,i=n)=>n%--i?p(n,i):i==1
La tfonction a été remplacée par l' eval(...)instruction directement dans la ffonction.

Solution précédente:

p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

Exemple: f(6)

Production: 29 I:2

Explication
J'utilise 3 fonctions

1 p : pour savoir si n est premier: p=n=>{for(i=n;n%--i&&i;);return 1==i}

2 t : connaître la longueur de la chaîne de Cunningham commençant par n de type I ou II en fonction du paramètre m qui sera 1 ou -1: t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3 f : compte les chaînes ( pour la boucle ) puis affiche le résultat

f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

pour la boucle : pour chaque numéro, la chaîne de Cunningham (I puis II si nécessaire) est valide si

• le nombre est premier
• le prédécesseur n'est pas premier
• le successeur est premier