Primarios XOR negativos

9

Hace aproximadamente un año, se le pidió que encontrara los primos XOR . Estos son números cuyos únicos factores son 1 y ellos mismos cuando se realiza la multiplicación XOR en la base 2 . Ahora vamos a condimentar un poco las cosas.

Vamos a encontrar los primos XOR en la base -2

Convirtiendo a Base -2

Base -2 es muy similar a cualquier otra base. El lugar más a la izquierda es el lugar 1 (1 = (-2) 0 ), al lado está el lugar -2s (-2 = (-2) 1 ), al lado está el lugar 4s (4 = (-2 ) 2 ), y así sucesivamente. La gran diferencia es que los números negativos se pueden representar en la base -2 sin ningún signo negativo.

Aquí hay algunos ejemplos de conversiones:

Decimal | Base -2
-----------------
 6      |   11010
-7      |    1001
 12     |   11100
-15     |  110001

Adición XOR en Base -2

La adición de XOR en Base -2 es más o menos lo mismo que la adición de XOR en binario. Simplemente convierta el número a Base -2 y XOR cada dígito en su lugar. (Esto es lo mismo que la adición sin el carry)

Aquí hay un ejemplo trabajado paso a paso:

(Usaremos el símbolo +'para indicar la adición de Base -2 XOR)

Comience en la base 10:

6 +' -19

Convertir a base -2:

11010 +' 10111

Agréguelos sin llevar:

   11010
+' 10111
---------
   01101

Convierta su resultado nuevamente en la base 10:

-3

Multiplicación XOR en Base -2

Una vez más, la multiplicación XOR en base -2 es casi lo mismo que la multiplicación XOR en binario. Si no está familiarizado con XOR multiplicación en base 2 hay una excelente explicación aquí le sugiero que tome un vistazo a la primera.

La multiplicación XOR en Base -2 es lo mismo que realizar una multiplicación larga en base -2, excepto cuando se trata del último paso en lugar de sumar todos los números con un tradicional +que usa el +'que definimos anteriormente.

Aquí hay un ejemplo elaborado a continuación:

Comience en decimal:

8 *' 7

Convierte a Base -2:

11000 *' 11011

Configurar una división larga:

   11000
*' 11011
---------

Multiplica el primer número por cada lugar en el segundo

      11000
*'    11011
------------
      11000
     11000
        0
   11000
  11000

Suma todos los resultados usando la adición base -2 XOR

       11000
*'     11011
-------------
       11000
      11000
         0
    11000
+' 11000
-------------
   101101000

Convierta el resultado a decimal:

280

El reto

Su desafío es verificar si un número es un primo XOR en la base -2. Un número es un primo XOR en base -2 si el único par de enteros que se multiplican en base es 1 y él mismo. (1 no es primo)

Tomará un número y generará un valor booleano, verdadero si la entrada es un primo XOR en base -2 falso de lo contrario.

Las soluciones se puntuarán en bytes con el objetivo de alcanzar el menor número de bytes.

Casos de prueba

Los siguientes son todos los primos XOR en la base -2:

-395
-3
-2
 3
 15
 83

Los siguientes no son primos XOR en la base -2:

-500
-4
 0
 1
 258
 280
Ad Hoc Garf Hunter
fuente
258parece igual-2 *' -129 = 10 *' 10000011
JungHwan Min
@JungHwanMin mi mal que se suponía que uno estaba en la otra categoría. Pido disculpas si esto te ha causado algún problema.
Ad Hoc Garf Hunter

Respuestas:

3

Mathematica, 156101 bytes

IrreduciblePolynomialQ[FromDigits[{#}//.{a_,p___}/;a!=1&&a!=0:>{-⌊a/2⌋,a~Mod~2,p},x],Modulus->2]&

Como se indicó aquí , esto funciona porque la multiplicación XOR es esencialmente una multiplicación en el anillo polinomial F_2.

Explicación

{#}//.{a_,p___}/;a!=1&&a!=0:>{-⌊a/2⌋,a~Mod~2,p}

Comenzar con {input}. Reemplazar repetidamente un número a(excepto 0 y 1) por amod 2 y anteponer -floor (a / 2), hasta que no cambie. Esto calcula la entrada en la base -2.

FromDigits[ ... ,x]

Cree un polinomio usando los dígitos del número base -2, usando xcomo variable. p.ej{1, 1, 0} ->x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]

Compruebe si el polinomio resultante es irreducible, con módulo 2.

Versión anterior (156 bytes)

If[#==1,1,Outer[FromDigits[BitXor@@(#~ArrayPad~{i++,--l}&)/@Outer[i=0;l=m;1##&,##],-2]&,k=Tuples[{0,1},m=Floor@Log2[8Abs@#~Max~1]]~Drop~{2},k,1,1]]~FreeQ~#&

Lista de primos

Aquí hay una lista de bases -2 XOR primos entre -1000 y 1000 (pastebin)

JungHwan Min
fuente