Un primo de Pillai es un número primo $p$ para el que existe un positivo $m$tal que $(m! + 1) \equiv 0 \:(\text{mod } p)$$p \not\equiv 1\:(\text{mod }m)$

En otras palabras, un número entero es un primo de Pillai si es un número primo , si existe otro número entero positivo tal que el factorial de , más es divisible por y si no es divisible por .$p$$m$$m$$1$$p$$p - 1$$m$

Dado un entero positivo como entrada, decida si es un primo Pillai. La secuencia de los primos de Pillai es OEIS A063980 .

Por ejemplo, es primo de Pillai porque:$23$

• Es un número primo, que tiene solo 2 factores.
• $m = 14$ y satisfacer las condiciones anteriores: y no divide ; y tampoco divide 22 .$m = 18$$23 \mid (14! + 1)$$14$$22$$23 \mid (18! + 1)$$18$$22$

Casos de prueba

Verdad:

23
59
83
109
139
593

Falsy

5 5
7 7
8
73
89
263
437

Para los casos de verdad, las m respectivas son [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].

Puede seguir el formato estándar de salida del problema de decisión (es decir, valores de verdad / falsedad) o tener un valor consistente para primos de Pillai y un valor no consistente de otra manera o viceversa .

Puede competir en cualquier lenguaje de programación y puede tomar entradas y proporcionar salidas a través de cualquier método estándar , mientras toma nota de que estas lagunas están prohibidas por defecto. Este es el código de golf , por lo que gana el envío más corto (en bytes) para cada idioma .

Python 2 , 115 111 110 109 bytes

^{-6 bytes gracias al 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)

Pruébalo en línea!

Las funciones constan de dos partes ~-n%x<1or~f(x)%n>0que verifican si n no cumple con las "condiciones de Pillai", y n%x>0para la validación principal.
Después de que allse aplica a ambos elementos, el primer elemento contendrá False/ 0si no es un "número Pillai" válida, y el segundo contendrá True/ 1si nes primo.
Estos se pasan a los cmpque volverán -1en este cenario (es un Pillai prime válido). Las otras combinaciones [[0, 0], [1, 0], [1, 1]]volverán 0o1

Jalea , 11 8 bytes

Ṗ!%ẹ’ḍ’E

Devuelve 0 para Pillai prime, 1 de lo contrario.

Pruébalo en línea!

Cómo 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))

Pruébalo en línea!

Brachylog , 19 bytes

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

Pruébalo en línea!

Traducción bastante directa de la pregunta:

ṗ          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 gracias a FrownyFrog

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

Pruébalo en línea!

Explicación:

                        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)

La salida es por presencia o ausencia de un error.

Pruébalo en línea!

Python 2 , 109107 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)

Pruébalo en línea!

Explicación

La lencuentra el factorial del número aprobada en, por lo 5que los rendimientos de entrada120 .

Las all(p%i for i in range(2,p-1))verificaciones para ver si un número es primo, ignoramos 0 y 1 ya que nuestras otras condiciones ya las descartan.

Finalmente, usamos any(~-p%m>-~l(m)%p==0for m in range(2,p))para iterar a través de todas las posibles m buscando para ver si alguna satisface nuestras necesidades. ~-psignifica p+1. Luego verificamos si es mayor que -~l(m)%p(lo que se traduce en (m!-1)%p, y luego lo comparamos 0. Básicamente ~-p%mdebe ser mayor que 0 y -~l(m)%pdebe ser 0.

Fuentes

• Factorial por 0xKirill

Mejoras

• De 109 a 107, Sr. Xcoder

como probablemente puede ver en el enlace tio, no todos los casos pasan, eso es porque js no puede manejar números grandes, si tal requisito existe, trataré de implementarlo :)

hay una doble verificación F%n>n-2&(F+1)%n<1para evitar falsos positivos (pero no al revés con problemas de números grandes de js, realmente necesitamos (F+1)%n<1números más pequeños que reduzcan el recuento de bytes de la solución a 60

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

• gracias a Arnauld por reducir en 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

Pruébalo en línea!

Brachylog , 13 bytes

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

Pruébalo en línea!

Tiene éxito para los primos de Pillai, proporcionando el m más pequeño a través de la variable de salida, y falla por cualquier otra cosa. Dado que una gran parte de cómo esto ahorra bytes sobre la solución de sundar es que calcula repetidamente las factorizaciones primas de algunos números bastante grandes, es bastante lento en entradas más grandes. (Probablemente ejecutaré esos casos en mi instalación local de Brachylog una vez que mi computadora portátil no esté funcionando con la batería).

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

El módulo de teoría de números tiene los predicados como funciones integradas (is_pillai en realidad devuelve 0 o la m más pequeña, por lo que también resuelve A063828). El código subyacente de C y Perl no tiene golf (por supuesto). El código C se ve así:

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

(genéricamente reemplace UV con uint64_t o similar, y HALF_WORD decide si podemos optimizar el mulmod en operaciones nativas simples).

El código puro de Perl es similar 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;}

Pruébalo en línea!

Whispers 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

Pruébalo en línea!

Esto devuelve una lista vacía para números primos que no son Pillai, y una lista no vacía de lo contrario.

Cómo funciona

Whispers fue diseñado para la manipulación de números reales / complejos, con un poco de comandos de matriz agregados para una buena medida, de ahí el uso repetido de Eachiterar sobre las listas generadas.

Un poco de historia sobre Whispers:

Whispers es ligeramente diferente en su ruta de ejecución a la mayoría de los otros idiomas. En lugar de trabajar a través de cada línea linealmente, solo ramificándose en condicionales, Whispers comienza en la última línea del archivo que comienza con >(las reglas son un poco más complicadas que eso, pero eso es todo lo que necesitamos saber por ahora), y el significado de los números difieren, dependiendo de si la línea comienza con >o >>.

Si la línea comienza con >, como > 1o > Input, esta es una línea constante : devuelve el mismo valor cada vez. Aquí, los números representan su forma numérica, por lo que la primera línea siempre devolverá 1 cuando se llame.

>>Sin embargo, si la línea comienza con , los números se tratan como referencias a otras líneas, más o menos como llamadas a funciones, si lo desea. Por ejemplo, en la línea >> 1…2, esto no ejecuta el …comando en los enteros 1 y 2 , sino en los valores devueltos por las líneas 1 y 2 . En este caso, esos valores son el número entero 1 y cualquier entero que se nos pase como entrada.

Para este ejemplo, consideremos la entrada de 23 . Tenga en cuenta que, debido al preprocesamiento de Whispers, la segunda línea ( > Input) se convierte a> 23 .

Nuestro primer comando está en la línea 3: >> 1…2. …es un rango diádico, en este caso de 1 a 23 , produciendo {1, 2, ... 22, 23} . A continuación, saltamos a las líneas 9 a 12 :

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

Aquí tenemos 4 Eachenunciados consecutivos , cada uno de los cuales itera sobre el resultado anterior, esencialmente mapeando los 4 comandos sobre la matriz en la línea 3 : el rango. Las primeras tres declaraciones son mapas simples, con líneas 4 , 5 y 6 :

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

Estos tres comandos, sobre un número entero n , producen (n! +1) ∣x , donde ! denota factorial , ∣ denota divisibilidad y x es la entrada. Finalmente, la línea 12 tiene una estructura de mapa diádico .

Una estructura de mapa diádico toma tres enteros: el objetivo, el izquierdo y el derecho, cada uno indexa a otras líneas. Aquí, comprimimos la izquierda y la derecha para producir una lista de pares, luego reducimos cada par mediante el comando diádico (el objetivo). Aquí, si la entrada es 23 , las listas son {1, 2, ... 22, 23} y {0, 0, ... 1, 0} y el comando es

>> L⋅R

que multiplica el argumento izquierdo por el derecho. Esto produce una matriz de enteros, con 0 en los índices de enteros cuyos factoriales incrementados no son divisibles por las entradas, y el índice original donde están. Vamos a llamar a esta matriz A . A continuación, eliminamos los 0 s de A tomando la diferencia establecida entre {0} y A :

> {0}
>> 12∖13

Con nuestro ejemplo de entrada, esto produce el conjunto {14, 18, 22} . A continuación, tomamos el resto de la entrada que se divide por cada valor en el conjunto, y verificamos si ese resto no es igual a 1 :

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

Nuevamente, tenemos una lista de 0 o 1 sy necesitamos eliminar los 0 sy reemplazar los 1 s con los valores originales. Aquí repetimos el código que vimos arriba, pero con >> 18∖13más que con 12. Finalmente, lanzamos este conjunto resultante a una lista para una verificación final. Desafortunadamente, nuestro código también debe rechazar números compuestos que cumplan con todos estos criterios, como 437 . Entonces agregamos nuestra verificación final, multiplicando nuestra lista final por la primalidad de la entrada. Debido a cómo funciona la multiplicación de Python en las listas, 0 la reemplaza con una lista vacía y 1 no tiene ningún efecto. Entonces calculamos la primalidad de la entrada, multiplicamos eso por la lista de m s para la entrada y salida del 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}

Aquí 23x significaría 23r1 y la fracción 23/1, entonces todos los demás; prueba:

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

TIO no ha implementado la biblioteca System.Numerics en su lanzamiento de Mono, por lo que puede ver los resultados ¡ Pruébelo en línea! Aquí en cambio.

Explicación:

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

Salidas 11si la entrada es un primer pillai, de lo contrario 00, 01o10

Explicación:

                                         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

Pruébalo en línea!