Un Pillai premier est un nombre premier $p$ pour lequel il existe un certain positif tel que et .$m$$(m! + 1) \equiv 0 \:(\text{mod } p)$$p \not\equiv 1\:(\text{mod }m)$

En d'autres termes, un entier $p$ est un nombre premier de Pillai s'il s'agit d'un nombre premier , s'il existe un autre entier positif $m$ tel que la factorielle de $m$ , plus $1$ est divisible par $p$ et si $p - 1$ n'est pas divisible par $m$ .

Étant donné un entier positif en entrée, décidez s'il s'agit d'un nombre premier de Pillai. La séquence des nombres premiers de Pillai est OEIS A063980 .

Par exemple, est un nombre premier de Pillai car:$23$

• C'est un nombre premier, n'ayant que 2 facteurs.
• $m = 14$ et remplissent les conditions ci-dessus: et ne divise pas ; et ne divise pas non plus .23 ∣ ( 14 ! + 1 ) 14 22 23 ∣ ( 18 ! + 1 ) 18 $m = 18$$23 \mid (14! + 1)$$14$$22$$23 \mid (18! + 1)$$18$$22$

Cas de test

Vérité:

23
59
83
109
139
593

Falsy:

5
sept
8
73
89
263
437

Pour les cas véridiques, les m respectifs sont [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Vous pouvez soit suivre le format de sortie standard de problème de décision (c'est-à-dire, les valeurs véridiques / fausses), soit avoir une valeur cohérente pour les nombres premiers Pillai et une valeur non cohérente sinon ou vice versa .

Vous pouvez concurrencer dans n'importe quel langage de programmation et pouvez prendre des entrées et fournir des sorties par n'importe quelle méthode standard , tout en prenant note que ces failles sont interdites par défaut. Il s'agit de code-golf , donc la soumission la plus courte (en octets) pour chaque langue l' emporte.

Python 2 , 115 111 110 109 octets

^{-6 octets grâce à M. Xcoder}

lambda n:n>2and cmp(*map(all,zip(*[[n%x==1or~f(x)%n,n%x]for x in range(2,n)])))<0
f=lambda x:0**x or x*f(x-1)

Essayez-le en ligne!

Les fonctions se composent de deux parties ~-n%x<1or~f(x)%n>0qui vérifient si n elles ne satisfont pas aux "conditions Pillai", et n%x>0pour la validation principale.
Après cela , allon applique aux deux articles, le premier élément contiendra False/ 0s'il est valide « nombre Pillai », et le second contiendra True/ 1si nest premier.
Ceux-ci sont transmis à cmpcelui qui reviendra -1dans ce cenario (est un premier Pillai valide). Les autres combinaisons [[0, 0], [1, 0], [1, 1]]reviendront 0ou1

Gelée , 11 8 octets

Ṗ!%ẹ’ḍ’E

Renvoie 0 pour Pillai prime, 1 sinon.

Essayez-le en ligne!

Comment ça fonctionne

Ṗ!%ẹ’ḍ’E  Main link. Argument: n

Ṗ         Pop; yield [1, ..., n-1].
 !        Take the factorial of each integer.
  %       Take the factorials modulo p.
   ẹ’     Find all indices of n-1.
     ḍ’   Test n-1 for divisibility by each of these indices.
       E  Return 1 if all of the resulting Booleans are equal (all 1 means there is
          no suitable m, all 0 means n is not prime), 0 if they are different.

Pari / GP , 44 octets

p->isprime(p)&&sum(m=2,p,p%m-1&&!((m!+1)%p))

Essayez-le en ligne!

Brachylog , 19 octets

ṗ>.ḟ+₁;?%0&-₁;.%>0∧

Essayez-le en ligne!

Traduction assez simple de la question:

ṗ          Input is a prime
>.         And output is a number less than the input
ḟ+₁;?%0    And output's factorial + 1 mod input is 0
&-₁;.%>0   And input - 1 mod output is greater than 0
∧          No further constraints

J , 30 26 octets

-4 octets grâce à FrownyFrog

1 e.i.((|1+!)~<1~:|)1&p:*]

Essayez-le en ligne!

Explication:

                        1&p:*]      checks if the number is prime and if not sets it to 0
                   1~:|             checks if p is not 1 mod m
           (|1+!)~                  m factorial plus 1 modulo n
                  <                 are both conditions met?  
       i.                           generates successive m's (a list 0..n-1)
   1 e.                             1's are at the indices of m, so if there's 1 - Pillai

Python 2 , 65 64 53 52 octets

f=lambda n,k=3,m=2:~m%n<1<n%k%(n%~-k)or f(n,k+1,m*k)

La sortie s'effectue via la présence ou l'absence d'une erreur.

Essayez-le en ligne!

Python 2 , 109 107 octets

lambda p:any(~-p%m>~l(m)%p<1for m in range(2,p))*all(p%i for i in range(2,p-1))
l=lambda a:0**a or a*l(a-1)

Essayez-le en ligne!

Explication

Le ltrouve la factorielle du nombre transmis, de sorte 5que l'entrée revient 120.

Les all(p%i for i in range(2,p-1))vérifications pour voir si un nombre est premier, nous ignorons 0 et 1 car nos autres conditions les excluent déjà.

Enfin, nous utilisons any(~-p%m>-~l(m)%p==0for m in range(2,p))pour parcourir tous les m potentiels qui cherchent à voir s'ils satisfont à nos besoins. ~-psignifie p+1. Ensuite, nous vérifions s'il est supérieur à -~l(m)%p(ce qui se traduit par (m!-1)%p, puis nous le comparons à 0. Fondamentalement, il ~-p%mdoit être supérieur à 0 et -~l(m)%pdoit être égal à 0.

Sources

• Factorial par 0xKirill

Améliorations

• De 109 à 107, M. Xcoder

comme vous pouvez probablement le voir dans le lien tio, tous les cas ne passent pas, c'est parce que js ne peut pas gérer les grands nombres, si une telle exigence existe mal, essayez de la mettre en œuvre :)

il y a une double vérification F%n>n-2&(F+1)%n<1pour éviter les faux positifs (mais pas l'inverse avec les problèmes de grand nombre js, nous avons vraiment besoin (F+1)%n<1de nombres plus petits, ce qui réduit le nombre d'octets de la solution à 60

JavaScript (Node.js) , 90 88 86 72 68 octets

• merci à Arnauld pour avoir réduit de 1 octet

f=(n,F=i=2,g=0)=>n%i?f(n,F*=++i,g|=F%n>n-2&(F+1)%n<1&~-n%i>0):i==n*g

Essayez-le en ligne!

Brachylog , 13 octets

>.ḟ+₁ḋ∋?-₁f≡ⁿ

Essayez-le en ligne!

Réussit pour les nombres premiers Pillai, fournissant le plus petit m via la variable de sortie, et échoue pour autre chose. Puisqu'une grande partie de la façon dont cela économise des octets par rapport à la solution de Sundar est qu'il calcule à plusieurs reprises les factorisations principales de certains très gros nombres, c'est assez incroyablement lent sur des entrées plus grandes. (Je vais probablement exécuter ces cas sur mon installation Brachylog locale une fois que mon ordinateur portable n'est pas alimenté par batterie.)

 .               The output
>                is less than the input,
       ?         the input
      ∋          is an element of
     ḋ           the prime factorization of
 .               the output's
  ḟ              factorial
   +₁            plus one,
           ≡ⁿ    and the output is not an element of
          f      the list of all factors of
       ?         the input
        -₁       minus one.

[Perl], 45 octets

use ntheory":all";is_prime($n)&&is_pillai($n)

Le module de théorie des nombres a les prédicats en tant que fonctions intégrées (is_pillai renvoie en fait 0 ou le plus petit m, donc résout A063828 également). Le code C et Perl sous-jacent n'est pas joué (bien sûr). Le code C ressemble à:

UV pillai_v(UV n) {
  UV v, fac = 5040 % n;
  if (n == 0) return 0;
  for (v = 8; v < n-1 && fac != 0; v++) {
    fac = (n < HALF_WORD) ? (fac*v) % n : mulmod(fac,v,n);
    if (fac == n-1 && (n % v) != 1)
      return v;
  }
  return 0;
}

(remplacez génériquement UV par uint64_t ou similaire, et HALF_WORD décide si nous pouvons optimiser le mulmod en opérations natives simples).

Le code Perl pur est similaire à:

sub is_pillai {
  my $p = shift;
  return 0 if $p <= 2;
  my($pm1, $nfac) = ($p-1, 5040 % $p);
  for (my $n = 8; $n < $p; $n++) {
    $nfac = mulmod($nfac, $n, $p);
    return $n if $nfac == $pm1 && ($p % $n) != 1;
  }
  0;
}

C (gcc) , 64 octets

f(n,k,m,r){for(k=m=1,r=0;k<n;m=m*++k%n)r|=m/~-n<<(n%k==1);r/=3;}

Essayez-le en ligne!

Whispers v2 , 230 octets

> 1
> Input
>> 1…2
>> L!
>> L+1
>> L∣2
>> L⋅R
>> 2%L
>> Each 4 3
>> Each 5 9
>> Each 6 10
>> Each 7 11 3
> {0}
>> 12∖13
>> Each 8 14
>> L≠1
>> Each 16 15
>> Each 7 17 15
>> 18∖13
>> [19]
>> 2’
>> 21⋅20
>> Output 22

Essayez-le en ligne!

Cela renvoie une liste vide pour les nombres premiers non Pillai, et une liste non vide sinon.

Comment ça fonctionne

Whispers a été conçu pour être manipulé sur des nombres réels / complexes, avec un peu de commandes de tableau ajoutées pour faire bonne mesure, d'où l'utilisation répétée de Eachpour parcourir les listes générées.

Un peu d'histoire sur Whispers:

Whispers est légèrement différent dans son chemin d'exécution vers la plupart des autres langages. Plutôt que de parcourir chaque ligne de façon linéaire, en ne ramifiant que les conditions, Whispers commence sur la dernière ligne du fichier commençant par >(les règles sont légèrement plus compliquées que cela, mais c'est tout ce que nous devons savoir pour l'instant), et la signification des nombres diffèrent selon que la ligne commence par >ou >>.

Si la ligne commence par >, comme > 1ou > Input, c'est une ligne constante - elle renvoie la même valeur à chaque fois. Ici, les nombres représentent leur forme numérique, donc la première ligne retournera toujours 1 lors de l'appel.

Si la ligne commence par >>cependant, les nombres sont traités comme des références à d'autres lignes, sorte d'appels de fonction similaires, si vous voulez. Par exemple, dans la ligne >> 1…2, cela n'exécute pas la …commande sur les entiers 1 et 2 , mais plutôt sur les valeurs renvoyées par les lignes 1 et 2 . Dans ce cas, ces valeurs sont l'entier 1 et quel que soit l'entier que nous transmettons en entrée.

Pour cet exemple, considérons l'entrée de 23 . Gardez à l'esprit qu'en raison du prétraitement de Whispers, la deuxième ligne ( > Input) est convertie en > 23.

Notre première commande est en ligne 3: >> 1…2. …est une gamme dyadique, dans ce cas de 1 à 23 , donnant {1, 2, ... 22, 23} . Ensuite, nous sautons aux lignes 9 à 12 :

>> Each 4 3
>> Each 5 9
>> Each 6 10
>> Each 7 11 3

Ici, nous avons 4 Eachdéclarations consécutives , chacune d'elles répétant le résultat précédent, mappant essentiellement les 4 commandes sur le tableau de la ligne 3 : la plage. Les trois premiers énoncés sont de simples cartes, avec les lignes 4 , 5 et 6 :

>> L!
>> L+1
>> L∣2

Ces trois commandes, sur un entier n , donnent (n! +1) ∣x , où ! dénote factorielle , ∣ dénote la divisibilité et x est l'entrée. Enfin, la ligne 12 a une structure de carte dyadique .

Une structure de carte dyadique prend trois entiers: la cible, la gauche et la droite, chacun indexe sur d'autres lignes. Ici, nous zip la gauche et la droite pour produire une liste de paires, puis réduisons chaque paire par la commande dyadique (la cible). Ici, si l'entrée est 23 , les listes sont {1, 2, ... 22, 23} et {0, 0, ... 1, 0} et la commande est

>> L⋅R

qui multiplie l'argument de gauche par la droite. Cela produit un tableau d'entiers, avec 0 aux index des entiers dont les factorielles incrémentées ne sont pas divisibles par les entrées, et l'index d'origine où elles se trouvent. Nous appellerons ce tableau A . Ensuite, nous supprimons les 0 de A en prenant la différence définie entre {0} et A :

> {0}
>> 12∖13

Avec notre exemple d'entrée, cela produit l'ensemble {14, 18, 22} . Ensuite, nous prenons le reste de l'entrée divisé par chaque valeur de l'ensemble et vérifions si ce reste n'est pas égal à 1 :

>> 2%L
>> Each 8 14
>> L≠1
>> Each 16 15

Encore une fois, nous avons une liste de 0 ou de 1 s et devons supprimer les 0 et remplacer les 1 par les valeurs d'origine. Ici, nous répétons le code que nous avons vu ci-dessus, mais avec >> 18∖13plutôt que 12. Enfin, nous avons converti cet ensemble résultant en une liste pour une vérification finale. Malheureusement, notre code doit également rejeter les nombres composites qui répondent à tous ces critères, tels que 437 . Nous ajoutons donc notre contrôle final, en multipliant notre liste finale par la primauté de l'entrée. En raison du fonctionnement de la multiplication Python sur les listes, 0 la remplace par une liste vide et 1 n'a aucun effet. Nous calculons donc la primauté de l'entrée, multiplions cela par la liste de ms pour l'entrée et la sortie du résultat final:

>> 2’
>> 21⋅20
>> Output 22

APL (NARS), 65 caractères, 130 octets

{∼0π⍵:0⋄m←⎕ct⋄⎕ct←0⋄r←⍬≢a/⍨{0≠⍵∣p}¨a←k/⍨0=⍵∣1+!k←⍳p←¯1+⍵⋄⎕ct←m⋄r}

Ici 23x cela signifierait 23r1 et donc la fraction 23/1, donc tous les autres; tester:

  f←{∼0π⍵:0⋄m←⎕ct⋄⎕ct←0⋄r←⍬≢a/⍨{0≠⍵∣p}¨a←k/⍨0=⍵∣1+!k←⍳p←¯1+⍵⋄⎕ct←m⋄r}
  f¨23x 59x 83x 109x 139x 593x
1 1 1 1 1 1 
  f¨5x 7x 73x 89x 263x 437x
0 0 0 0 0 0 

C # (Visual C # Interactive Compiler) , 138 + 22 = 160 octets

n=>Enumerable.Range(2,n-2).All(x=>n%x>0)&Enumerable.Range(1,n).Any(x=>{BigInteger a,b=1;for(a=1;a<=x;a++)b*=a;return(b+1)%n<1&(n-1)%x>0;})

TIO n'a pas implémenté la bibliothèque System.Numerics dans sa version de Mono, vous pouvez donc voir les résultats Essayez-le en ligne! Ici à la place.

Explication:

using System.Numerics; //necessary to handle large numbers created by the factorials

return 
    Enumerable.Range(2,n-2).All(x=>n%x>0)       // is prime
    &
    Enumerable.Range(1,n).Any(x=>
    {
        BigInteger a,b=1;for(a=1;a<=x;a++)b*=a; //b = a!
        return (b+1)%n<1
               &                                //the condition for PPs
               (n-1)%x>0;             
    });

CJam , 37 octets

ri_mp\[_{_M)m!)@%!\_M)%1=!@&\}fM]);:|

Sorties 11si l'entrée est un pilier premier, sinon 00, 01ou10

Explication:

                                         e# Explanation | Stack
ri_mp\[_{_M)m!)@%!\_M)%1=!@&\}fM]);:|    e# Whole code | Example input: 593
ri                                       e# Read input as integer | 593
  _                                      e# Duplicate | 593 593
   mp                                    e# Is it prime? | 593 1
     \                                   e# Swap top two stack elements | 1 593
      [                         ]        e# Delimits an array. Any operations that
                                         e# push a value are placed into the array
       _                                 e# Duplicate | 1 593 [593]
        {                    }fM         e# A for loop from 0 to (n-1) looped through
                                         e# variable M
         _                               e# Duplicate top stack value | ...[593 593]
          M)                             e# Get M+1, as if we try M=0 we get an error
                                         e# | ...[593 593 1]
            m!                           e# Factorial | ...[593 593 1]
              )                          e# Add one | ...[593 593 2]
               @                         e# Rotate stack | ...[593 2 593]
                %                        e# Modulus | ...[593 2]
                 !                       e# Equal to 0? | ...[593 0]
                  \_                     e# Swap and duplicate | ...[0 593 593]
                    M)                   e# Push M+1 | ...[0 593 593 1]
                      %                  e# Modulus | ...[0 593 0]
                       1=!               e# Not equal to 1? | ...[0 593 1]
                          @              e# Rotate | ...[593 1 0]
                           &             e# AND | ...[593 0]
                            \            e# Swap | ...[0 593]
                             }     
                                ]
                                 );      e# Dump and discard last element
                                         e# | 1 593 [...]
                                   :|    e# Flatten array with OR | 1 1
                                         e# Implicit output

Essayez-le en ligne!