Пиллаи простое простое число $p$ , для которых существует некоторый положительный $m$ такое , что $(m! + 1) \equiv 0 \:(\text{mod } p)$ и$p \not\equiv 1\:(\text{mod }m)$ .

Другими словами, целое число является простым Пиллаи , если это простое число , если существует еще одно натуральное число т такое , что факториала из м , плюс 1 делится на р и если р - 1 не делится на т .$p$$m$$m$$1$$p$$p - 1$$m$

Учитывая положительное целое число в качестве входных данных, решите, является ли это простое число Пиллаи. Последовательность простых чисел Пиллаи OEIS A063980 .

Например, - простое число Пиллаи, потому что:$23$

• Это простое число, имеющее только 2 фактора.
• и m = 18 удовлетворяют вышеуказанным условиям: 23 ∣ ( 14 ! + 1 ) и 14 не делит 22 ; итоже не делят.$m = 14$$m = 18$$23 \mid (14! + 1)$$14$$22$18 $23 \mid (18! + 1)$$18$$22$

Контрольные примеры

Truthy:

23
59
83
109
139
593

Falsy:

5
7
8
73
89
263
437

Для случаев truthy, соответствующих M «s являются [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Вы можете либо следовать стандартному формату вывода проблемы решения (то есть значениям истинности / ложности), либо иметь непротиворечивое значение для простых чисел Пиллаи и непоследовательное значение в противном случае, или наоборот .

Вы можете соревноваться на любом языке программирования и можете принимать и выводить данные любым стандартным методом , при этом отмечая, что эти лазейки по умолчанию запрещены. Это код-гольф , поэтому выигрывает самое короткое представление (в байтах) для каждого языка .

Python 2 , 115 111 110 109 байт

^{-6 байт благодаря мистеру 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)

Попробуйте онлайн!

Функции состоят из двух частей, ~-n%x<1or~f(x)%n>0которые проверяют, если n не удовлетворяет «условиям Пиллаи», и n%x>0для первичной проверки.
После этого allприменяются к обеим пунктам, первый элемент будет содержать False/ 0если есть действительный «Пиллаи номер», а второй будет содержать True/ , 1если nпервично.
Они передаются тому, cmpчто вернется -1в этом кенарио (это действительное простое число Пиллаи). Другие комбинации [[0, 0], [1, 0], [1, 1]]вернутся 0или1

Желе , 11 8 байт

Ṗ!%ẹ’ḍ’E

Возвращает 0 для простого Пиллаи, 1 в противном случае.

Попробуйте онлайн!

Как это устроено

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

Par / GP , 44 байта

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

Попробуйте онлайн!

Брахилог , 19 байт

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

Попробуйте онлайн!

Довольно простой перевод вопроса:

ṗ          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 байт

-4 байта благодаря FrownyFrog

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

Попробуйте онлайн!

Объяснение:

                        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 байта

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

Вывод через наличие или отсутствие ошибки.

Попробуйте онлайн!

Python 2 , 109 107 байт

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)

Попробуйте онлайн!

объяснение

lНаходит факториал числа принятого в, так 5как входные возвращается 120.

В all(p%i for i in range(2,p-1))проверяет , является ли число простым, мы игнорируем 0 и 1 , как наши другие условия уже исключают те вне.

Наконец, мы используем, any(~-p%m>-~l(m)%p==0for m in range(2,p))чтобы перебрать все потенциальные m, чтобы посмотреть, удовлетворяет ли какой-либо из наших потребностей. ~-pзначит p+1. Затем мы проверяем, является ли оно больше чем -~l(m)%p(что переводится как (m!-1)%p, и затем мы сравниваем его с 0. В основном ~-p%mдолжно быть больше 0 и -~l(m)%pдолжно быть 0.

источники

• Факториал от 0xKirill

улучшения

• С 109 по 107 г-н Xcoder

как вы, вероятно, можете видеть из ссылки tio, не все случаи проходят, потому что js не может обрабатывать большие числа, если такое требование существует, попробуйте выполнить его :)

Существует двойная проверка F%n>n-2&(F+1)%n<1для предотвращения ложных срабатываний (но не в случае больших проблем с js, мы действительно нуждаемся (F+1)%n<1в меньших числах, которые уменьшают число байтов решения до 60

JavaScript (Node.js) , 90 88 86 72 68 байт

• спасибо Арно, за сокращение на 1 байт

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

Попробуйте онлайн!

Брахилог , 13 байт

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

Попробуйте онлайн!

Успешен для простых чисел Пиллаи, обеспечивая наименьшее m через выходную переменную, и завершается неудачей для чего-либо еще. Поскольку большая часть того, как это экономит байты по сравнению с решением sundar, заключается в том, что он многократно вычисляет простые факторизации некоторых довольно больших чисел, это довольно невероятно медленно для больших входных данных. (Вероятно, я буду запускать эти случаи на моей локальной установке Brachylog, когда мой ноутбук не работает от батареи.)

 .               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 байт

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

Модуль теории чисел имеет предикаты как встроенные функции (is_pillai фактически возвращает либо 0, либо наименьшее m, поэтому также решает A063828). Базовый код C и Perl не разыгрывается (конечно). Код C выглядит так:

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

(обычно заменяют UV на uint64_t или аналогичный, и HALF_WORD решает, можем ли мы оптимизировать mulmod в простые нативные операции).

Чистый код Perl похож на:

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 байта

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

Попробуйте онлайн!

Whispers v2 , 230 байт

> 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

Попробуйте онлайн!

Это возвращает пустой список для простых чисел Pillai, и непустой список в противном случае.

Как это устроено

Whispers был разработан для манипулирования действительными / комплексными числами, с небольшим количеством команд массива, добавленных для хорошей меры, следовательно, многократное использование Eachдля итерации по сгенерированным спискам.

Немного предыстории о Whispers:

Шепот немного отличается по пути выполнения от большинства других языков. Вместо того, чтобы работать по каждой строке линейно, только с ветвлением в условных выражениях, Whispers начинается с последней строки в файле, начинающейся с >(правила немного сложнее, но это все, что нам нужно знать на данный момент), и значения чисел различаются в зависимости от того, начинается ли строка с >или >>.

Если строка начинается с >, например, > 1или> Input , это постоянная строка - она ​​каждый раз возвращает одно и то же значение. Здесь числа представляют их числовую форму, поэтому первая строка всегда будет возвращать 1 при вызове.

Однако, если строка начинается с >>, числа обрабатываются как ссылки на другие строки, вроде вызовов функций, если хотите. Например, в строке >> 1…2это не выполняет …команду для целых чисел 1 и 2 , а скорее для значений, возвращаемых из строк 1 и 2 . В этом случае эти значения являются целым числом 1 и любым целым числом, которое мы передаем в качестве входных данных.

Для этого примера давайте рассмотрим ввод 23 . Имейте в виду, что из-за предварительной обработки Whispers вторая строка ( > Input) преобразуется в > 23.

Наша первая команда в строке 3: >> 1…2. …является диадическим диапазоном, в данном случае от 1 до 23 , что дает {1, 2, ... 22, 23} . Далее перейдем к строкам с 9 по 12 :

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

Здесь у нас есть 4 последовательных Eachоператора, каждое из которых повторяется по предыдущему результату, по существу отображая 4 команды в массиве в строке 3 : диапазон. Первые три утверждения - это простые карты со строками 4 , 5 и 6 :

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

Эти три команды над целым числом n дают (n! +1) ∣x , где ! обозначает факториал , ∣ обозначает делимость, а х - вход. Наконец, строка 12 имеет структуру двоичной карты .

Диадическая карта структура занимает три целых числа: цель, левые и право, каждый из индексов других линий. Здесь мы сжимаем влево и вправо, чтобы создать список пар, а затем сокращаем каждую пару с помощью диадической команды (цель). Здесь, если ввод 23 , списки {1, 2, ... 22, 23} и {0, 0, ... 1, 0} и команда

>> L⋅R

который умножает левый аргумент на правый. Это создает массив целых чисел, с 0 по индексам целых чисел, чьи факториалы увеличиваются, не делятся на входы и исходный индекс, где они находятся. Мы будем называть этот массив A . Затем мы удаляем 0 с из A , беря разницу между {0} и A :

> {0}
>> 12∖13

В нашем примере ввода это дает набор {14, 18, 22} . Затем мы берем остаток от входных данных, деленных на каждое значение в наборе, и проверяем, не равен ли этот остаток 1 :

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

Опять же, у нас есть список из 0 или 1 с, и нам нужно удалить 0 с и заменить 1 с исходными значениями. Здесь мы повторяем код, который мы видели выше, но >> 18∖13вместо 12. Наконец, мы приводим этот результирующий набор к списку для окончательной проверки. К сожалению, наш код также должен отклонять составные числа, которые соответствуют всем этим критериям, например 437 . Таким образом, мы добавляем нашу последнюю проверку, умножая наш окончательный список на простоту ввода. Из-за того, как умножение Python работает со списками, 0 заменяет его пустым списком, а 1 не имеет никакого эффекта. Таким образом, мы рассчитываем простоту ввода, умножьте это на список мs для ввода и вывода окончательного результата:

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

APL (NARS), 65 символов, 130 байтов

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

Здесь 23x это будет означать 23r1 и, следовательно, дробь 23/1, то есть все остальные; тестовое задание:

  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 #) , 138 + 22 = 160 байт

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 не реализовала библиотеку System.Numerics в своем выпуске Mono, поэтому вы можете увидеть результаты. Попробуйте онлайн! Вот вместо

Объяснение:

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 байт

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

Выходные данные, 11если input - это простое число, иначе 00, 01или10

Объяснение:

                                         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

Попробуйте онлайн!