Liczba pierwsza Pillai jest liczbą pierwszą $p$ dla której istnieje pewna liczba dodatnia $m$ taka że $(m! + 1) \equiv 0 \:(\text{mod } p)$$p \not\equiv 1\:(\text{mod }m)$

Innymi słowy, całkowita jest liczbą pierwszą Pillai jeśli jest liczbą pierwszą , czy istnieje inny dodatnią liczbą całkowitą tak, że czynnikowe z plus jest podzielna przez i jeśli nie jest podzielna przez .$p$$m$$m$$1$$p$$p - 1$$m$

Biorąc pod uwagę dodatnią liczbę całkowitą jako dane wejściowe, zdecyduj, czy jest to liczba pierwsza Pillai. Sekwencja liczb pierwszych Pillai to OEIS A063980 .

Na przykład jest liczbą pierwszą Pillai, ponieważ:$23$

• Jest to liczba pierwsza, mająca tylko 2 czynniki.
• $m = 14$ i spełniają powyższe warunki: i nie dzieli ; i również nie dzielą .$m = 18$$23 \mid (14! + 1)$$14$$22$$23 \mid (18! + 1)$$18$$22$

Przypadki testowe

Prawda:

23
59
83
109
139
593

Falsy:

5
7
8
73
89
263
437

W przypadkach truthy, odpowiednich M „s są [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Możesz postępować zgodnie ze standardowym formatem wyjściowym problemu decyzyjnego (tj. Wartościami prawda / fałsz) lub mieć spójną wartość liczb pierwszych Pillai i niespójną wartość w przeciwnym razie lub odwrotnie .

Możesz konkurować w dowolnym języku programowania i możesz przyjmować dane wejściowe i generować dane wyjściowe za pomocą dowolnej standardowej metody , zwracając uwagę, że te luki są domyślnie zabronione. To jest golf golfowy , więc wygrywa najkrótsze przesłanie (w bajtach) dla każdego języka .

Python 2 , 115 111 110 109 bajtów

^{-6 bajtów dzięki 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)

Wypróbuj online!

Funkcje składają się z dwóch części, ~-n%x<1or~f(x)%n>0które weryfikują, czy n nie spełniają „warunków Pillai”, i n%x>0dla pierwszej weryfikacji.
Następnie allnakłada się obu elementów, pierwszy element będzie zawierać False/ 0jeżeli nie jest poprawny „numer Pillai”, a druga będzie zawierała True/ 1jeśli njest pierwszorzędna.
Są one przekazywane, aby cmppowrócić -1w tym cenario (jest prawidłową liczbą pierwszą Pillai). Inne kombinacje [[0, 0], [1, 0], [1, 1]]powrócą 0lub1

Galaretka , 11 8 bajtów

Ṗ!%ẹ’ḍ’E

Zwraca 0 dla liczby pierwszej Pillai, w przeciwnym razie 1 .

Wypróbuj online!

Jak to działa

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

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

Wypróbuj online!

Brachylog , 19 bajtów

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

Wypróbuj online!

Dość proste tłumaczenie pytania:

ṗ          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 bajtów

-4 bajty dzięki FrownyFrog

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

Wypróbuj online!

Wyjaśnienie:

                        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 bajty

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

Wyjście odbywa się przez obecność lub brak błędu.

Wypróbuj online!

Python 2 , 109 107 bajtów

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)

Wypróbuj online!

Wyjaśnienie

lZnajdzie silnię liczby przyjętej w, tak 5jak zwrotów wejściowych 120.

Do all(p%i for i in range(2,p-1))sprawdza, czy liczba jest pierwsza, ignorujemy 0 i 1 jak inne nasze warunki już wykluczyć te out.

Wreszcie, używamy any(~-p%m>-~l(m)%p==0for m in range(2,p))do iteracji przez wszystkie potencjalne strony, aby sprawdzić, czy którekolwiek spełniają nasze potrzeby. ~-pśrodki p+1. Następnie sprawdzamy, czy jest on większy niż -~l(m)%p(co tłumaczy (m!-1)%p, a następnie porównujemy 0. Zasadniczo ~-p%mmusi być większy niż 0 i -~l(m)%pmusi wynosić 0.

Źródła

• Silnia przez 0xKirill

Ulepszenia

• Od 109 do 107, pan Xcoder

jak zapewne widać na łączu tio, nie wszystkie przypadki przebiegają pomyślnie, to dlatego, że js nie może obsłużyć dużych liczb, jeśli takie wymagania istnieją, spróbuj go wdrożyć :)

istnieje podwójna kontrola, F%n>n-2&(F+1)%n<1aby zapobiec fałszywie dodatnim (ale nie na odwrót w przypadku problemów z dużą liczbą js, naprawdę potrzebujemy (F+1)%n<1mniejszych liczb, które zmniejszają liczbę bajtów rozwiązania do 60

JavaScript (Node.js) , 90 88 86 72 68 bajtów

• dzięki Arnauldowi za zmniejszenie o 1 bajt

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

Wypróbuj online!

Brachylog , 13 bajtów

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

Wypróbuj online!

Udaje się w przypadku liczb pierwszych Pillai, zapewniając najmniejsze m poprzez zmienną wyjściową, i kończy się niepowodzeniem dla czegokolwiek innego. Ponieważ duża część tego, jak oszczędza to bajty w porównaniu z rozwiązaniem sundarowym, polega na tym, że wielokrotnie oblicza podstawowe faktoryzacje niektórych dość dużych liczb, jest dość niewiarygodnie powolny przy większych wejściach. (Prawdopodobnie uruchomię te przypadki na mojej lokalnej instalacji Brachylog, gdy mój laptop nie będzie zasilany z baterii).

 .               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 bajtów

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

Moduł teorii liczb ma predykaty jako funkcje wbudowane (is_pillai faktycznie zwraca 0 lub najmniejsze m, więc rozwiązuje również A063828). Podstawowy kod C i Perl nie jest golfem (oczywiście). Kod C wygląda następująco:

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

(generalnie zamień UV na uint64_t lub podobny, a HALF_WORD decyduje, czy możemy zoptymalizować mulmod do prostych natywnych operacji).

Czysty kod Perla jest podobny do:

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 bajty

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

Wypróbuj online!

Whispers v2 , 230 bajtów

> 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

Wypróbuj online!

Zwraca to pustą listę liczb pierwszych niepobranych w Pillai, aw przeciwnym razie niepustą listę.

Jak to działa

Szepty zostały zaprojektowane do manipulowania liczbami rzeczywistymi / złożonymi, z niewielką ilością poleceń tablicowych dodanych dla dobrego pomiaru, stąd wielokrotne użycie Eachiteracji po wygenerowanych listach.

Trochę tła na temat szeptów:

Szepty różnią się nieco ścieżką wykonania od większości innych języków. Zamiast pracować liniowo nad każdą linią, tylko rozgałęziając się w warunkach, Szepty zaczynają się od ostatniej linii w pliku zaczynając od >(reguły są nieco bardziej skomplikowane, ale to wszystko, co na razie musimy wiedzieć) i znaczenie liczb różnią się w zależności od tego, czy linia zaczyna się od, >czy >>.

Jeśli linia zaczyna się od >, na przykład > 1lub > Input, jest to linia stała - za każdym razem zwraca tę samą wartość. Tutaj liczby reprezentują ich postać liczbową, więc pierwsza linia zawsze zwraca 1, gdy zostanie wywołana.

Jeśli linia zaczyna się od >>, liczby są traktowane jako odniesienia do innych linii, podobnie jak wywołania funkcji, jeśli chcesz. Na przykład w wierszu >> 1…2nie wykonuje …polecenia na liczbach całkowitych 1 i 2 , ale na wartościach zwracanych z wierszy 1 i 2 . W tym przypadku tymi wartościami są liczba całkowita 1 i dowolna liczba całkowita, którą przekazujemy jako dane wejściowe.

W tym przykładzie rozważmy dane wejściowe 23 . Należy pamiętać, że z powodu przetwarzania wstępnego Szeptów druga linia ( > Input) jest konwertowana na> 23 .

Nasza pierwsza komenda jest na linii 3: >> 1…2. …oznacza zakres dynamiczny, w tym przypadku od 1 do 23 , dając {1, 2, ... 22, 23} . Następnie przechodzimy do linii od 9 do 12 :

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

Tutaj mamy 4 kolejne Eachinstrukcje, z których każda iteruje w stosunku do poprzedniego wyniku, zasadniczo mapując 4 polecenia na tablicę w linii 3 : zakres. Pierwsze trzy stwierdzenia to proste mapy z wierszami 4 , 5 i 6 :

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

Te trzy polecenia powyżej liczby całkowitej n dają (n! +1) ∣x , gdzie ! oznacza silnię , ∣ oznacza podzielność, a x oznacza dane wejściowe. Wreszcie linia 12 ma mapę diadadową strukturę .

Dwójkowym mapa struktura zajmuje trzy liczby całkowite: cel, w lewo iw prawo, każdy indeksów na innych liniach. Tutaj spakowujemy w lewo i w prawo, aby utworzyć listę par, a następnie zmniejszamy każdą parę za pomocą polecenia dyadic (celu). Tutaj, jeśli wartością wejściową jest 23 , listy to {1, 2, ... 22, 23} i {0, 0, ... 1, 0}, a polecenie to

>> L⋅R

co zwielokrotnia lewy argument przez prawy. W ten sposób powstaje tablica liczb całkowitych, gdzie 0 przy indeksach liczb całkowitych, których silni przyrosty nie są podzielne przez dane wejściowe, i pierwotny indeks tam, gdzie są. Zadzwonimy tej tablicy A . Następnie usuwamy 0 z A , biorąc ustaloną różnicę między {0} a A :

> {0}
>> 12∖13

Przy naszym przykładowym wprowadzeniu tworzy to zestaw {14, 18, 22} . Następnie bierzemy pozostałą część danych wejściowych dzieloną przez każdą wartość w zestawie i sprawdzamy, czy ta reszta nie jest równa 1 :

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

Ponownie mamy listę 0 lub 1 s i musimy usunąć 0 i zastąpić je 1 oryginalnymi wartościami. Tutaj powtarzamy kod, który widzieliśmy powyżej, ale >> 18∖13zamiast 12. Na koniec rzutujemy ten wynikowy zestaw na listę w celu ostatecznego sprawdzenia. Niestety nasz kod musi również odrzucać liczby zespolone spełniające wszystkie te kryteria, takie jak 437 . Więc dodajemy naszą ostatnią kontrolę, mnożąc naszą ostateczną listę przez pierwotność danych wejściowych. Ze względu na to, jak działa mnożenie Pythona na listach, 0 zastępuje je pustą listą, a 1 nie ma wpływu. Obliczamy więc pierwotność danych wejściowych, pomnóż ją przez listę ms dla danych wejściowych i wyjściowych:

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

APL (NARS), 65 znaków, 130 bajtów

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

Tutaj 23x oznaczałoby to 23r1, a więc ułamek 23/1, czyli wszystkie pozostałe; test:

  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 # (interaktywny kompilator Visual C #) , 138 + 22 = 160 bajtów

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 nie wdrożyło biblioteki System.Numerics w swoim wydaniu Mono, więc możesz zobaczyć wyniki Wypróbuj online! Tutaj zamiast tego.

Wyjaśnienie:

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 bajtów

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

Wyjścia 11jeśli wejście jest najlepszym Pillai, poza 00, 01lub10

Wyjaśnienie:

                                         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

Wypróbuj online!