Eine Pillai-Primzahl ist eine Primzahl $p$ für die es ein positives $m$ so dass und.$(m! + 1) \equiv 0 \:(\text{mod } p)$$p \not\equiv 1\:(\text{mod }m)$

Mit anderen Worten, eine ganze Zahl ist eine Pillai-Primzahl, wenn es eine Primzahl ist , wenn eine andere positive ganze Zahl so dass die Fakultät von plus durch teilbar ist und wenn nicht durch teilbar ist .$p$$m$$m$$1$$p$$p - 1$$m$

Entscheiden Sie bei einer positiven Ganzzahl als Eingabe, ob es sich um eine Pillai-Primzahl handelt. Die Sequenz der Pillai-Primzahlen ist OEIS A063980 .

Zum Beispiel ist eine Pillai-Primzahl, weil:$23$

• Es ist eine Primzahl mit nur 2 Faktoren.
• $m = 14$ und erfüllen die obigen Bedingungen: und teilt ; und teilen auch nicht.23 | ( 14 ! + 1 ) 14 22 23 | ( 18 ! + 1 ) 18 $m = 18$$23 \mid (14! + 1)$$14$$22$$23 \mid (18! + 1)$$18$$22$

Testfälle

Wahrheit:

23
59
83
109
139
593

Falsch:

5
7
8
73
89
263
437

Für die wahrheitsgemäßen Fälle sind die jeweiligen m 's [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Sie können entweder dem Standardformat für die Ausgabe von Entscheidungsproblemen folgen (dh Wahrheits- / Fehlerwerte) oder einen konsistenten Wert für Pillai-Primzahlen und einen ansonsten nicht konsistenten Wert oder umgekehrt haben .

Sie können in jeder Programmiersprache antreten und über jede Standardmethode Eingaben und Ausgaben vornehmen. Beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind. Dies ist Codegolf , daher gewinnt die kürzeste Übermittlung (in Bytes) für jede Sprache .

Python 2 , 115 111 110 109 Bytes

^{-6 Bytes dank Mr. 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)

Probieren Sie es online!

Die Funktionen bestehen aus zwei Teilen ~-n%x<1or~f(x)%n>0, die überprüfen, ob die "Pillai-Bedingungen" n nicht erfüllt sind, und n%x>0für die Erstvalidierung.
Danach allauf beiden Elemente angewandt wird, wird das erste Element enthalten False/ 0wenn es ist eine gültige „Pillai - Nummer“ und die zweiten enthält True/ 1wenn eine nPrimzahl ist.
Diese werden an cmpdas -1in diesem Cenario zurückgegeben (ist eine gültige Pillai-Primzahl). Die anderen Kombinationen [[0, 0], [1, 0], [1, 1]]geben 0oder zurück1

Jelly , 11 8 Bytes

Ṗ!%ẹ’ḍ’E

Gibt für Pillai prime 0 zurück , andernfalls 1 .

Probieren Sie es online!

Wie es funktioniert

Ṗ!%ẹ’ḍ’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 Bytes

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

Probieren Sie es online!

Brachylog , 19 Bytes

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

Probieren Sie es online!

Ziemlich einfache Übersetzung der Frage:

ṗ          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 Bytes

-4 Bytes dank FrownyFrog

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

Probieren Sie es online!

Erläuterung:

                        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 Bytes

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

Die Ausgabe erfolgt über das Vorhandensein oder Fehlen eines Fehlers.

Probieren Sie es online!

Python 2 , 109 107 Bytes

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)

Probieren Sie es online!

Erläuterung

Der lfindet die Fakultät der übergebenen Zahl, so dass 5die Eingabe zurückkehrt 120.

Bei der all(p%i for i in range(2,p-1))Überprüfung, ob eine Zahl eine Primzahl ist, ignorieren wir 0 und 1, da unsere anderen Bedingungen diese bereits ausschließen.

Schließlich verwenden wir any(~-p%m>-~l(m)%p==0for m in range(2,p)), um alle potenziellen m zu durchlaufen, um zu sehen, ob irgendwelche unsere Bedürfnisse befriedigen. ~-pbedeutet p+1. Dann prüfen wir, ob es größer ist als -~l(m)%p(was übersetzt wird (m!-1)%p, und vergleichen es dann mit 0. Grundsätzlich ~-p%mmuss es größer als 0 sein und -~l(m)%pmuss 0 sein.

Quellen

• Factorial von 0xKirill

Verbesserungen

• Von 109 bis 107, Mr. Xcoder

Wie Sie wahrscheinlich im tio-Link sehen können, passieren nicht alle Fälle, das liegt daran, dass js keine großen Zahlen verarbeiten kann.

es gibt eine doppelte Prüfung F%n>n-2&(F+1)%n<1, um falsch positive zu verhindern (aber nicht umgekehrt bei Problemen mit großen Zahlen, wir brauchen wirklich (F+1)%n<1kleinere Zahlen, die die Anzahl der Lösungsbytes auf 60 reduzieren

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

• Danke an Arnauld für die Reduzierung um 1 Byte

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

Probieren Sie es online!

Brachylog , 13 Bytes

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

Probieren Sie es online!

Gelingt dies für Pillai-Primzahlen, wobei das kleinste m durch die Ausgabevariable bereitgestellt wird, und schlägt für alles andere fehl. Da ein großer Teil der Einsparungen von Bytes gegenüber der Sundar-Lösung darin besteht, dass wiederholt die Primfaktoren einiger ziemlich großer Zahlen berechnet werden, ist dies bei größeren Eingaben unglaublich langsam. (Ich werde diese Fälle wahrscheinlich auf meiner lokalen Brachylog-Installation ausführen, wenn mein Laptop nicht mit Batterie betrieben wird.)

 .               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 Bytes

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

Das Zahlentheorie-Modul hat die Prädikate als eingebaute Funktionen (is_pillai gibt entweder 0 oder das kleinste m zurück, löst also auch A063828). Der zugrunde liegende C- und Perl-Code wird (natürlich) nicht verwendet. Der C-Code sieht folgendermaßen aus:

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;
}

(Ersetzen Sie UV generisch durch uint64_t oder ähnliches, und HALF_WORD entscheidet, ob wir den Mulmod in einfache native Operationen optimieren können).

Der reine Perl-Code ähnelt:

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 Bytes

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;}

Probieren Sie es online!

Flüstert v2 , 230 Bytes

> 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

Probieren Sie es online!

Dies gibt eine leere Liste für Nicht-Pillai-Primzahlen und ansonsten eine nicht leere Liste zurück.

Wie es funktioniert

Whispers wurde für die Manipulation von reellen / komplexen Zahlen entwickelt, wobei ein wenig Array-Befehle hinzugefügt wurden, um eine gute Messung zu ermöglichen, daher die wiederholte Verwendung von Each die generierten Listen durchlaufen werden können.

Hintergrundinformationen zu Whispers:

Whispers unterscheidet sich in seinem Ausführungspfad geringfügig von den meisten anderen Sprachen. Anstatt jede Zeile linear durchzuarbeiten und nur nach Bedingungen zu verzweigen, beginnt Whispers in der letzten Zeile der Datei mit >(die Regeln sind etwas komplizierter, aber das ist alles, was wir jetzt wissen müssen) und den Bedeutungen von Zahlen unterscheiden sich je nachdem, ob die Zeile mit >oder beginnt >>.

Wenn die Zeile mit oder beginnt >, ist dies eine konstante Zeile. Sie gibt jedes Mal den gleichen Wert zurück. Hier stellen Zahlen ihre numerische Form dar, sodass die erste Zeile immer 1 zurückgibt> 1> Input zurückgibt.

Wenn die Zeile >>jedoch mit beginnt , werden Zahlen als Verweise auf andere Zeilen behandelt, sozusagen als Funktionsaufrufe. In der Zeile >> 1…2wird der …Befehl beispielsweise nicht für die Ganzzahlen 1 und 2 ausgeführt , sondern für die von den Zeilen 1 und 2 zurückgegebenen Werte . In diesem Fall sind diese Werte die Ganzzahl 1 und die ganze Zahl, die wir als Eingabe übergeben haben.

In diesem Beispiel betrachten wir die Eingabe von 23 . Beachten Sie, dass aufgrund der Vorverarbeitung von Whispers die zweite Zeile ( > Input) in konvertiert wird > 23.

Unser erster Befehl ist in Zeile 3: >> 1…2. …ist der dyadische Bereich, in diesem Fall von 1 bis 23 , was {1, 2, ... 22, 23} ergibt . Als nächstes fahren wir mit den Zeilen 9 bis 12 fort :

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

Hier haben wir 4 aufeinanderfolgende EachAnweisungen, von denen jede über das vorherige Ergebnis iteriert und im Wesentlichen die 4 Befehle über das Array in Zeile 3 abbildet : den Bereich. Die ersten drei Anweisungen sind einfache Karten mit den Zeilen 4 , 5 und 6 :

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

Diese drei Befehle, über eine ganze Zahl n , Ausbeuten (n! +1) |x , wo ! bezeichnet Fakultät , ∣ bezeichnet Teilbarkeit und x ist die Eingabe. Schließlich hat Linie 12 eine dyadische Kartenstruktur .

Eine dyadische Kartenstruktur besteht aus drei ganzen Zahlen: Das Ziel (links und rechts) verweist jeweils auf andere Zeilen. Hier zippen wir links und rechts, um eine Liste von Paaren zu erstellen, und reduzieren dann jedes Paar um den dyadischen Befehl (das Ziel). Wenn hier die Eingabe 23 ist , lauten die Listen {1, 2, ... 22, 23} und {0, 0, ... 1, 0}, und der Befehl lautet

>> L⋅R

Dies multipliziert das linke Argument mit dem rechten. Dies erzeugt ein Array von Ganzzahlen, wobei 0 bei den Indizes von Ganzzahlen, deren Fakultäten inkrementiert sind, nicht durch die Eingaben teilbar sind, und den ursprünglichen Index, in dem sie sich befinden. Wir werden dieses Array nennen A . Als nächst wir die entfernen 0 s von A , indem die Mengendifferenz zwischen {0} und A :

> {0}
>> 12∖13

In unserem Beispiel ergibt dies die Menge {14, 18, 22} . Als nächstes nehmen wir den Rest der Eingabe, der durch jeden Wert in der Menge geteilt wird, und prüfen, ob dieser Rest ungleich 1 ist :

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

Wieder haben wir eine Liste von entweder 0 oder 1 s und müssen die 0 s entfernen und die 1 s durch die ursprünglichen Werte ersetzen . Hier wiederholen wir den Code, den wir oben gesehen haben, aber mit >> 18∖13anstatt 12. Schließlich setzen wir diesen resultierenden Satz für eine abschließende Prüfung in eine Liste um. Leider muss unser Code auch zusammengesetzte Zahlen ablehnen, die alle diese Kriterien erfüllen, z. B. 437 . Also addieren wir unsere letzte Prüfung und multiplizieren unsere letzte Liste mit der Primalität der Eingabe. Aufgrund der Funktionsweise der Python-Multiplikation für Listen ersetzt 0 diese durch eine leere Liste und 1 hat keine Auswirkung. Wir berechnen also die Primalität der Eingabe und multiplizieren diese mit der Liste von ms für die Eingabe und Ausgabe des Endergebnisses:

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

APL (NARS), 65 Zeichen, 130 Byte

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

Hier 23x würde es bedeuten, 23r1 und damit den Bruch 23/1, also alle anderen; Prüfung:

  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 Byte

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 hat die System.Numerics-Bibliothek in seiner Version von Mono nicht implementiert, sodass Sie die Ergebnisse sehen können. Probieren Sie es online aus! Hier stattdessen.

Erläuterung:

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 Bytes

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

Ausgänge , 11wenn der Eingang ein pillai Primzahl ist, sonst 00, 01oder10

Erläuterung:

                                         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

Probieren Sie es online!