Étant donné un entier non négatif N, sortez le plus petit entier positif impair qui est un pseudoprime fort à toutes les premières Nbases premières.

Il s'agit de la séquence OEIS A014233 .

Cas de test (un index)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Les cas de test pour N > 13ne sont pas disponibles car ces valeurs n'ont pas encore été trouvées. Si vous parvenez à trouver le (s) terme (s) suivant (s) dans la séquence, assurez-vous de les soumettre à OEIS!

Règles

• Vous pouvez choisir de prendre Ncomme valeur indexée zéro ou une valeur indexée.
• Il est acceptable que votre solution ne fonctionne que pour les valeurs représentables dans la plage d'entiers de votre langue (donc jusqu'à N = 12pour les entiers 64 bits non signés), mais votre solution doit théoriquement fonctionner pour toute entrée en supposant que votre langue prend en charge les entiers de longueur arbitraire.

Contexte

Tout entier positif , même xpeut être écrit sous la forme x = d*2^soù dest impair. det speut être calculé en divisant à plusieurs reprises npar 2 jusqu'à ce que le quotient ne soit plus divisible par 2. dest ce quotient final, et sest le nombre de fois où 2 se divise n.

Si un entier positif nest premier, le petit théorème de Fermat déclare:

Dans tout champ fini Z/pZ (où pest un nombre premier), les seules racines carrées de 1sont 1et -1(ou, de manière équivalente, 1et p-1).

Nous pouvons utiliser ces trois faits pour prouver que l'une des deux déclarations suivantes doit être vraie pour un nombre premier n(où d*2^s = n-1et rest un entier dans [0, s)):

Le test de primalité de Miller-Rabin fonctionne en testant la contraposition de la revendication ci-dessus: s'il existe une base atelle que les deux conditions ci-dessus sont fausses, alors nn'est pas premier. Cette base as'appelle un témoin .

Désormais, tester chaque base en [1, n)serait extrêmement coûteux en temps de calcul pour les grandes n. Il existe une variante probabiliste du test de Miller-Rabin qui ne teste que certaines bases choisies au hasard dans le champ fini. Cependant, il a été découvert que le test uniquement des abases primaires est suffisant, et donc le test peut être effectué de manière efficace et déterministe. En fait, toutes les bases principales n'ont pas besoin d'être testées - seul un certain nombre est requis, et ce nombre dépend de la taille de la valeur testée pour la primalité.

Si un nombre insuffisant de bases premières est testé, le test peut produire des faux positifs - des nombres entiers composites impairs où le test ne parvient pas à prouver leur composition. Plus précisément, si une base ane parvient pas à prouver la composition d'un nombre composé impair, ce nombre est appelé un pseudoprime fort à baser a. Ce défi consiste à trouver les nombres composites impairs qui sont des pseudoprimes forts pour toutes les bases inférieures ou égales au Nth nombre premier (ce qui revient à dire qu'ils sont des pseudoprimes forts pour toutes les bases premières inférieures ou égales au Nth nombre premier) .

C, 349 295 277 267 255 octets

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Prend une entrée basée sur 1 sur stdin, par exemple:

echo "1" | ./millerRabin

Il ne va certainement pas découvrir de nouvelles valeurs dans la séquence de sitôt, mais il fait le travail. MISE À JOUR: maintenant encore plus lent!

• Légèrement plus rapide et plus court, en s'inspirant de la réponse de Neil A ( a^(d*2^r) == (a^d)^(2^r))
• Significativement plus lent à nouveau après avoir réalisé que toutes les solutions à ce défi seront impaires, il n'est donc pas nécessaire d'appliquer explicitement que nous vérifions uniquement les nombres impairs.
• Maintenant, en utilisant GCC __int128, qui est plus court que unsigned long longtout en travaillant avec de plus grands nombres! Également sur les machines peu endiennes, le printf avec %llufonctionne toujours bien.

Moins minifié

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

(Obsolète) ventilation

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Comme mentionné, cela utilise une entrée basée sur 1. Mais pour n = 0, il produit 9, qui suit la séquence connexe https://oeis.org/A006945 . Plus maintenant; maintenant il se bloque sur 0.

Devrait fonctionner pour tout n (au moins jusqu'à ce que la sortie atteigne 2 ^ 64) mais est incroyablement lent. Je l'ai vérifié sur n = 0, n = 1 et (après beaucoup d'attente), n = 2.

Python 2, 633 465 435 292 282 275 256 247 octets

0 indexé

Questionnez votre implémentation et essayez quelque chose de nouveau

La conversion d'une fonction en programme permet d'économiser quelques octets d'une manière ou d'une autre ...

Si Python 2 me donne un moyen plus court de faire la même chose, je vais utiliser Python 2. La division est par défaut un entier, donc un moyen plus facile de diviser par 2, et printn'a pas besoin de parenthèses.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Essayez-le en ligne!

Python est notoirement lent par rapport à d'autres langages.

Définit un test de division d'essai pour l'exactitude absolue, puis applique à plusieurs reprises le test de Miller-Rabin jusqu'à ce qu'un pseudoprime soit trouvé.

Essayez-le en ligne!

EDIT : Enfin joué la réponse

EDIT : utilisé minpour le test de primalité de la division d'essai et l'a changé en a lambda. Moins efficace, mais plus court. De plus, je n'ai pas pu m'en empêcher et j'ai utilisé quelques opérateurs au niveau du bit (pas de différence de longueur). En théorie, cela devrait fonctionner (légèrement) plus rapidement.

EDIT : Merci @Dave. Mon éditeur m'a traîné. Je pensais que j'utilisais des tabulations mais il était converti en 4 espaces à la place. J'ai également passé en revue à peu près tous les conseils Python et les ai appliqués.

EDIT : Passé à l'indexation 0, me permet d'économiser quelques octets avec la génération des nombres premiers. A également repensé quelques comparaisons

EDIT : utilisé une variable pour stocker le résultat des tests au lieu des for/elseinstructions.

EDIT : Déplacé l' lambdaintérieur de la fonction pour éliminer le besoin d'un paramètre.

EDIT : converti en programme pour économiser des octets

EDIT : Python 2 me fait gagner des octets! Je n'ai pas non plus besoin de convertir l'entrée enint

Perl + Math :: Prime :: Util, 81 + 27 = 108 octets

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Courez avec -lpMMath::Prime::Util=:all(pénalité de 27 octets, aïe).

Explication

Ce n'est pas seulement Mathematica qui a une fonction intégrée pour pratiquement tout. Perl possède CPAN, l'un des premiers grands référentiels de bibliothèques, et qui possède une énorme collection de solutions prêtes à l'emploi pour des tâches comme celle-ci. Malheureusement, ils ne sont pas importés (ni même installés) par défaut, ce qui signifie que ce n'est fondamentalement jamais une bonne option pour les utiliser dans le code-golf , mais quand l'un d'eux correspond parfaitement au problème…

Nous courons à travers des entiers consécutifs jusqu'à ce qu'on trouve un qui est pas premier, mais une forte pseudopremier à toutes les bases de nombre entier de 2 au n e premier. L'option de ligne de commande importe la bibliothèque qui contient la fonction intégrée en question et définit également l'entrée implicite (ligne par ligne; Math::Prime::Utilpossède sa propre bibliothèque bignum intégrée qui n'aime pas les retours à la ligne dans ses entiers). Cela utilise l'astuce Perl standard d'utilisation $\(séparateur de ligne de sortie) comme variable afin de réduire les analyses maladroites et de permettre la génération implicite de la sortie.

Notez que nous devons utiliser is_provable_primeici pour demander un test premier déterministe plutôt que probabiliste. (Surtout étant donné qu'un test probabiliste premier utilise probablement Miller-Rabin en premier lieu, ce à quoi nous ne pouvons pas nous attendre à donner des résultats fiables dans ce cas!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 octets, en collaboration avec @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Courir avec -lpMntheory=:all(pénalité de 17 octets).

Cela utilise quelques astuces de golf Perl que je ne connaissais pas non plus (apparemment Math :: Prime :: Util a une abréviation!), Que je connaissais mais que je ne pensais pas utiliser ( }{pour sortir $\implicitement une fois, plutôt "$_$\"qu'implicitement chaque ligne) . Merci à @Dada de me les avoir signalés. A part ça, c'est identique.