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
fuente
258
parece igual-2 *' -129 = 10 *' 10000011
Respuestas:
Mathematica,
156101bytesComo se indicó aquí , esto funciona porque la multiplicación XOR es esencialmente una multiplicación en el anillo polinomial F_2.
Explicación
Comenzar con
{input}
. Reemplazar repetidamente un númeroa
(excepto 0 y 1) pora
mod 2 y anteponer -floor (a
/ 2), hasta que no cambie. Esto calcula la entrada en la base -2.Cree un polinomio usando los dígitos del número base -2, usando
x
como variable. p.ej{1, 1, 0}
->x^2 + x
Compruebe si el polinomio resultante es irreducible, con módulo 2.
Versión anterior (156 bytes)
Lista de primos
Aquí hay una lista de bases -2 XOR primos entre -1000 y 1000 (pastebin)
fuente