Sebuah Pillai prima adalah bilangan prima yang ada ada beberapa yang positif m sehingga ( m ! + 1 ) ≡ $p$$m$ dan p ≢ $(m! + 1) \equiv 0 \:(\text{mod } p)$ .$p \not\equiv 1\:(\text{mod }m)$

Dengan kata lain, integer adalah prima Pillai jika itu adalah bilangan prima , jika ada yang lain bilangan bulat positif m sehingga faktorial dari m , ditambah 1 habis dibagi p dan jika p - 1 tidak habis dibagi m .$p$$m$$m$$1$$p$$p - 1$$m$

Diberi bilangan bulat positif sebagai input, putuskan apakah itu adalah Pillai prime. Urutan bilangan prima Pillai adalah OEIS A063980 .

Misalnya, adalah Pillai prima karena:$23$

• Ini adalah bilangan prima, hanya memiliki 2 faktor.
• dan m = 18 memenuhi kondisi di atas: 23 | ( 14 ! + 1 ) dan 14 tidak membagi 22 ; 23 | ( 18 ! + 1 ) dan 18 tidak membagi 22 baik.$m = 14$$m = 18$$23 \mid (14! + 1)$$14$$22$$23 \mid (18! + 1)$$18$$22$

Uji kasus

Benar:

23
59
83
109
139
593

Falsy:

5
7
8
73
89
263
437

Untuk kasus truthy, masing-masing m s' adalah [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Anda dapat mengikuti format keluaran masalah keputusan standar (yaitu, nilai kebenaran / kepalsuan) atau memiliki nilai yang konsisten untuk bilangan prima Pillai dan nilai yang tidak konsisten jika tidak atau sebaliknya. .

Anda dapat bersaing dalam bahasa pemrograman apa pun dan dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah kode-golf , jadi pengiriman terpendek (dalam byte) untuk setiap bahasa menang.

Python 2 , 115 111 110 109 byte

^{-6 byte terima kasih kepada Tn. 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)

Cobalah online!

Fungsi terdiri dari dua bagian ~-n%x<1or~f(x)%n>0yang memverifikasi jika n tidak memenuhi "kondisi Pillai", dan n%x>0untuk validasi utama.
Setelah itu allditerapkan untuk kedua item, item pertama akan berisi False/ 0jika ada yang valid "Pillai nomor", dan yang kedua akan berisi True/ 1jika nperdana.
Ini diteruskan ke cmpyang akan kembali -1dalam skenario ini (adalah prime Pillai yang valid). Kombinasi lainnya [[0, 0], [1, 0], [1, 1]]akan kembali 0atau1

Jelly , 11 8 byte

Ṗ!%ẹ’ḍ’E

Mengembalikan 0 untuk Pillai prime, 1 sebaliknya.

Cobalah online!

Bagaimana itu bekerja

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

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

Cobalah online!

Brachylog , 19 byte

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

Cobalah online!

Terjemahan pertanyaan yang cukup mudah:

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

-4 byte, terima kasih kepada FrownyFrog

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

Cobalah online!

Penjelasan:

                        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 byte

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

Output adalah melalui ada atau tidak adanya kesalahan.

Cobalah online!

Python 2 , 109 107 byte

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)

Cobalah online!

Penjelasan

The lmenemukan faktorial dari jumlah berlalu dalam, sehingga5 sebagai hasil masukan 120.

Itu all(p%i for i in range(2,p-1)) memeriksa untuk melihat apakah nomor perdana, kita mengabaikan 0 dan 1 sebagai kondisi kami yang lain sudah mengesampingkan mereka.

Akhirnya, kita gunakan any(~-p%m>-~l(m)%p==0for m in range(2,p))untuk beralih melalui semua potensi yang dicari untuk melihat apakah ada yang memenuhi kebutuhan kita. ~-pberarti p+1. Kemudian kita periksa untuk melihat apakah itu lebih besar dari -~l(m)%p(yang diterjemahkan menjadi (m!-1)%p, dan kemudian kita bandingkan 0. Pada dasarnya ~-p%mharus lebih besar dari 0 dan -~l(m)%pharus 0.

Sumber

• Faktorial oleh 0xKirill

Perbaikan

• Dari 109 hingga 107, Mr. Xcoder

seperti yang mungkin Anda lihat di tautan tio tidak semua kasus lulus, itu karena js tidak dapat menangani angka besar, jika ada persyaratan seperti itu coba untuk mengimplementasikannya :)

ada pemeriksaan ganda F%n>n-2&(F+1)%n<1untuk mencegah false positive (tapi tidak sebaliknya dengan masalah angka js besar, kita benar-benar perlu (F+1)%n<1untuk angka yang lebih kecil dimana mengurangi jumlah byte solusi ke 60

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

• terima kasih kepada Arnauld untuk mengurangi 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

Cobalah online!

Brachylog , 13 byte

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

Cobalah online!

Berhasil untuk bilangan prima Pillai, menyediakan m terkecil melalui variabel output, dan gagal untuk hal lain. Karena sebagian besar dari cara ini menghemat byte daripada solusi sundar adalah bahwa ia berulang kali menghitung faktorisasi utama dari beberapa angka yang cukup besar, itu sangat lambat pada input yang lebih besar. (Saya mungkin akan menjalankan kasing-kasing itu pada instalasi Brachylog lokal saya setelah laptop saya tidak menggunakan daya baterai.)

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

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

Modul teori angka memiliki predikat sebagai fungsi bawaan (is_pillai sebenarnya mengembalikan 0 atau m terkecil, jadi selesaikan juga A063828). Kode C dan Perl yang mendasarinya tidak golf (tentu saja). Kode C terlihat seperti:

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

(ganti UV secara umum dengan uint64_t atau yang serupa, dan HALF_WORD memutuskan apakah kami dapat mengoptimalkan mulmod menjadi ops asli yang sederhana).

Kode Perl murni mirip dengan:

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 byte

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

Cobalah online!

Bisikan v2 , 230 byte

> 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

Cobalah online!

Ini mengembalikan daftar kosong untuk bilangan prima non-Pillai, dan daftar non-kosong sebaliknya.

Bagaimana itu bekerja

Whispers dirancang untuk manipulasi pada bilangan real / kompleks, dengan sedikit perintah array ditambahkan untuk ukuran yang baik, karenanya penggunaan berulang Eachuntuk beralih pada daftar yang dihasilkan.

Sedikit latar belakang tentang Whispers:

Bisikan sedikit berbeda di jalur eksekusi untuk sebagian besar bahasa lain. Daripada mengerjakan setiap baris secara linier, hanya bercabang di conditional, Whispers mulai pada baris terakhir dalam file yang dimulai dengan >(aturan sedikit lebih rumit dari itu, tapi hanya itu yang perlu kita ketahui untuk saat ini), dan arti angka berbeda, tergantung pada apakah baris dimulai dengan >atau >>.

Jika garis dimulai dengan >, seperti > 1atau > Input, ini adalah garis konstan - ia mengembalikan nilai yang sama setiap kali. Di sini, angka mewakili bentuk numeriknya, sehingga baris pertama akan selalu mengembalikan 1 ketika dipanggil.

>>Namun, jika saluran dimulai dengan , nomor diperlakukan sebagai referensi ke saluran lain, semacam panggilan fungsi yang serupa, jika Anda mau. Misalnya, dalam baris >> 1…2, ini tidak melakukan …perintah pada bilangan bulat 1 dan 2 , tetapi pada nilai yang dikembalikan dari baris 1 dan 2 . Dalam hal ini, nilai-nilai tersebut adalah bilangan bulat 1 dan bilangan bulat apa pun yang kami berikan sebagai input.

Untuk contoh ini, mari kita pertimbangkan input 23 . Perlu diingat bahwa, karena preprocess Whispers ', baris kedua ( > Input) dikonversi ke> 23 .

Perintah pertama kami adalah pada baris 3: >> 1…2. …adalah rentang diad, dalam hal ini dari 1 hingga 23 , menghasilkan {1, 2, ... 22, 23} . Selanjutnya, kita lewati ke baris 9 hingga 12 :

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

Di sini kita memiliki 4 Eachpernyataan konsektif , yang masing-masing diulang dari hasil sebelumnya, pada dasarnya memetakan 4 perintah di atas array pada baris 3 : kisaran. Tiga pernyataan pertama adalah peta sederhana, dengan baris 4 , 5 dan 6 :

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

Tiga perintah ini, di atas bilangan bulat n , menghasilkan (n! +1) ∣x , di mana ! menunjukkan faktorial , ∣ menunjukkan kelaikan dan x adalah input. Akhirnya, baris 12 memiliki struktur peta diad .

Sebuah peta diad struktur mengambil tiga bilangan bulat: target, kiri dan kanan, masing-masing indeks untuk jalur lainnya. Di sini, kita ritsleting kiri dan kanan untuk menghasilkan daftar pasangan, lalu kurangi setiap pasangan dengan perintah diad (target). Di sini, jika inputnya adalah 23 , daftarnya adalah {1, 2, ... 22, 23} dan {0, 0, ... 1, 0} dan perintahnya adalah

>> L⋅R

yang mengalikan argumen kiri dengan kanan. Ini menghasilkan array bilangan bulat, dengan 0 pada indeks bilangan bulat yang faktorialnya bertambah tidak dapat dibagi oleh input, dan indeks asli di mana mereka berada. Kami akan memanggil array ini A . Selanjutnya, kami menghapus 0 s dari A dengan mengambil perbedaan set antara {0} dan A :

> {0}
>> 12∖13

Dengan input contoh kami, ini menghasilkan set {14, 18, 22} . Selanjutnya kita mengambil sisa input yang dibagi dengan masing-masing nilai dalam set, dan memeriksa apakah sisanya tidak sama dengan 1 :

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

Sekali lagi, kami memiliki daftar 0 atau 1 dan perlu menghapus 0 dan mengganti 1 dengan nilai asli. Di sini kita ulangi kode yang kita lihat di atas, tetapi dengan >> 18∖13alih - alih 12. Akhirnya, kami melemparkan set hasil ini ke daftar untuk pemeriksaan akhir. Sayangnya, kode kami juga harus menolak angka gabungan yang mencapai semua kriteria ini, seperti 437 . Jadi kami menambahkan pemeriksaan terakhir kami, mengalikan daftar akhir kami dengan keutamaan input. Karena cara kerja penggandaan Python pada daftar, 0 menggantikannya dengan daftar kosong, dan 1 tidak berpengaruh. Jadi kita menghitung keutamaan input, kalikan dengan daftar muntuk input dan ouput hasil akhir:

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

APL (NARS), 65 karakter, 130 byte

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

Di sini 23x artinya 23r1 dan fraksi 23/1, jadi yang lainnya; uji:

  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 belum mengimplementasikan perpustakaan System.Numerics dalam rilisnya Mono, sehingga Anda dapat melihat hasilnya Coba online! Di sini sebagai gantinya.

Penjelasan:

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 byte

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

Keluaran 11jika input adalah pillai prime, jika tidak 00, 01atau10

Penjelasan:

                                         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

Cobalah online!