Um primo Pillai é um número primo para o qual existe algum positivo tal que e .$p$$m$$(m! + 1) \equiv 0 \:(\text{mod } p)$$p \not\equiv 1\:(\text{mod }m)$

Em outras palavras, um número inteiro $p$ é um primo Pillai se for um número primo , se existir outro número inteiro positivo $m$ tal modo que o fatorial de $m$ , mais $1$ seja divisível por $p$ se $p - 1$ não for divisível por $m$ .

Dado um número inteiro positivo como entrada, decida se é um primo Pillai. A sequência de primos Pillai é OEIS A063980 .

Por exemplo, $23$ é um primo de Pillai porque:

• É um número primo, com apenas 2 fatores.
• $m = 14$ e $m = 18$ satisfazem as condições acima: $23 \mid (14! + 1)$ e $14$ não divide $22$ ; $23 \mid (18! + 1)$ e $18$ também não dividem $22$ .

Casos de teste

Verdade:

23
59.
83
109
139
593

Falsy:

5
7
8
73
89
263
437

Para os casos de verdade, os respectivos m são [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Você pode seguir o formato de saída padrão do problema de decisão (ou seja, valores de verdade / falsidade) ou ter um valor consistente para primos Pillai e um valor não consistente, caso contrário ou vice-versa .

Você pode competir em qualquer linguagem de programação e pode receber e fornecer saída por qualquer método padrão , observando que essas brechas são proibidas por padrão. Isso é código-golfe , então a submissão mais curta (em bytes) para todos os idiomas vence.

Python 2 , 115 111 110 109 bytes

^{-6 bytes graças ao Sr. 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)

Experimente online!

As funções consistem em duas partes ~-n%x<1or~f(x)%n>0que verificam se n não satisfazem as "condições Pillai" e n%x>0para a validação principal.
Depois que allé aplicado a ambos os itens, o primeiro item conterá False/ 0se não é um "número Pillai" válido, eo segundo conterá True/ 1se né primo.
Estes são passados ​​para o cmpque retornará -1neste cenário (é um válido Pillai prime). As outras combinações [[0, 0], [1, 0], [1, 1]]retornarão 0ou1

Geléia , 11 8 bytes

Ṗ!%ẹ’ḍ’E

Retorna 0 para Pillai prime, 1 caso contrário.

Experimente online!

Como funciona

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

Experimente online!

Braquilog , 19 bytes

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

Experimente online!

Tradução bastante direta da pergunta:

ṗ          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 graças ao FrownyFrog

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

Experimente online!

Explicação:

                        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)

A saída é via presença ou ausência de um erro.

Experimente 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)

Experimente online!

Explicação

O llocaliza o fatorial do número passado, assim 5como a entrada retorna 120.

As all(p%i for i in range(2,p-1))verificações para ver se um número é primo, ignoramos 0 e 1, pois nossas outras condições já as excluem.

Finalmente, usamos any(~-p%m>-~l(m)%p==0for m in range(2,p))para percorrer todos os potenciais m procurando ver se algum satisfaz nossas necessidades. ~-pmeios p+1. Em seguida, verificamos se é maior que -~l(m)%p(o que se traduz em (m!-1)%pe depois o comparamos 0. Basicamente, ~-p%mdeve ser maior que 0 e -~l(m)%pdeve ser 0.

Fontes

• Fatorial por 0xKirill

Melhorias

• De 109 a 107, o Sr. Xcoder

como você provavelmente pode ver no link tio, nem todos os casos passam, isso é porque js não pode lidar com grandes números, se esse requisito existir, tente implementá-lo :)

há uma verificação dupla F%n>n-2&(F+1)%n<1para evitar falsos positivos (mas não o contrário com problemas de grande número de js, precisamos realmente (F+1)%n<1de números menores, pois reduz a contagem de bytes da solução para 60

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

• graças a Arnauld por reduzir em 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

Experimente online!

Braquilog , 13 bytes

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

Experimente online!

É bem-sucedido nos primos Pillai, fornecendo o menor m através da variável de saída, e falha em qualquer outra coisa. Como grande parte de como isso economiza bytes em relação à solução da sundar é que ele calcula repetidamente as fatorações primárias de alguns números bastante grandes, é incrivelmente lento em entradas maiores. (Provavelmente executarei esses casos na instalação local do Brachylog quando o laptop não estiver usando a bateria.)

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

O módulo da teoria dos números tem os predicados como funções internas (is_pillai na verdade retorna 0 ou o menor m, e também resolve o A063828). O código C e Perl subjacente não é jogado (é claro). O código C se parece com:

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

(substitua UV genericamente por uint64_t ou similar, e HALF_WORD decide se podemos otimizar o mulmod em operações simples nativas).

O código Perl puro é semelhante a:

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

Experimente online!

Sussurros 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

Experimente online!

Isso retorna uma lista vazia para números primos não Pillai e uma lista não vazia caso contrário.

Como funciona

O Whispers foi projetado para manipulação em números reais / complexos, com um pouco de comandos de matriz adicionados para uma boa medida, daí o uso repetido de Eachpara iterar nas listas geradas.

Um pouco de experiência no Whispers:

O Whispers é um pouco diferente no caminho de execução para a maioria dos outros idiomas. Em vez de trabalhar linearmente cada linha, apenas ramificando-se em condicionais, o Whispers começa na última linha do arquivo começando com >(as regras são um pouco mais complicadas que isso, mas é tudo o que precisamos saber por enquanto) e os significados dos números diferem, dependendo se a linha começa com >ou >>.

Se a linha começar com >, como > 1ou > Input, essa é uma linha constante - ela retornará o mesmo valor todas as vezes. Aqui, os números representam sua forma numérica; portanto, a primeira linha sempre retornará 1 quando chamada.

Se a linha começar, no >>entanto, os números serão tratados como referências a outras linhas, como chamadas de função, se você desejar. Por exemplo, na linha >> 1…2, isso não executa o …comando nos números inteiros 1 e 2 , mas nos valores retornados das linhas 1 e 2 . Nesse caso, esses valores são o número inteiro 1 e qualquer número inteiro que passamos como entrada.

Neste exemplo, vamos considerar a entrada 23 . Lembre-se de que, devido ao pré-processamento do Whispers, a segunda linha ( > Input) é convertida em > 23.

Nosso primeiro comando é na linha 3: >> 1…2. …é o intervalo diádico, neste caso de 1 a 23 , resultando em {1, 2, ... 22, 23} . Em seguida, pulamos para as linhas 9 a 12 :

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

Aqui temos quatro Eachinstruções consectutivas , cada uma das quais itera sobre o resultado anterior, mapeando essencialmente os 4 comandos sobre a matriz na linha 3 : o intervalo. As três primeiras instruções são mapas simples, com as linhas 4 , 5 e 6 :

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

Esses três comandos, sobre um número inteiro n , produz (n! +1) ∣x , onde ! denota factorial , | denota divisbility e x é a entrada. Finalmente, a linha 12 possui uma estrutura de mapa diádico .

Uma estrutura de mapa diádico leva três números inteiros: o alvo, a esquerda e a direita, cada um indexa para outras linhas. Aqui, fechamos a esquerda e a direita para produzir uma lista de pares e depois reduzimos cada par pelo comando diádico (o destino). Aqui, se a entrada for 23 , as listas são {1, 2, ... 22, 23} e {0, 0, ... 1, 0} e o comando é

>> L⋅R

que multiplica o argumento da esquerda pela direita. Isso produz uma matriz de números inteiros, com 0 nos índices de números inteiros cujos fatoriais incrementados não são divisíveis pelas entradas e o índice original onde eles estão. Vamos chamar essa matriz A . Em seguida, vamos remover os 0 s de A , tendo a diferença de conjunto entre {0} e A :

> {0}
>> 12∖13

Com nosso exemplo de entrada, isso produz o conjunto {14, 18, 22} . A seguir, pegamos o restante da entrada sendo dividido por cada valor no conjunto e verificamos se esse restante não é igual a 1 :

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

Novamente, temos uma lista de 0 ou 1 se precisamos remover os 0 se substituir os 1 pelos valores originais. Aqui repetimos o código que vimos acima, mas com um >> 18∖13pouco do que 12. Por fim, lançamos esse conjunto resultante em uma lista para uma verificação final. Infelizmente, nosso código também deve rejeitar números compostos que atendem a todos esses critérios, como 437 . Portanto, adicionamos nossa verificação final, multiplicando nossa lista final pela primalidade da entrada. Devido à forma como a multiplicação do Python funciona nas listas, 0 o substitui por uma lista vazia e 1 não tem efeito. Então calculamos a primalidade da entrada, multiplique isso pela lista de ms para a entrada e saída do resultado final:

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

APL (NARS), 65 caracteres, 130 bytes

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

Aqui 23x, significaria 23r1 e, portanto, a fração 23/1, e todos os outros; teste:

  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 # (compilador interativo do Visual C #) , 138 + 22 = 160 bytes

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

O TIO não implementou a biblioteca System.Numerics no lançamento do Mono, para que você possa ver os resultados Experimente online! Aqui em vez disso.

Explicação:

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]);:|

Saídas 11se a entrada for um pillai prime, caso contrário 00, 01ou10

Explicação:

                                         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

Experimente online!