# Negative XOR primes

About a year ago you were asked to find the XOR primes. These are numbers whose only factors are 1 and themselves when performing XOR multiplication in base 2. Now were are going to spice things up a bit.

We are going to find the XOR primes in base -2

## Converting to Base -2

Base -2 is a lot like every other base. The left most place is the 1s place (1 = (-2)0), next to that its the -2s place (-2 = (-2)1), next to that is the 4s place (4 = (-2)2), and so on and so forth. The big difference is that negative numbers can be represented in base -2 without any negative sign.

Here are some example conversions:

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


## XOR addition in Base -2

XOR addition in Base -2 is pretty much the same as XOR addition in binary. You simply convert the number to Base -2 and XOR each digit in place. (This is the same as addition without the carry)

Here is an example worked through step by step:

(We will use the symbol +' to indicate Base -2 XOR addition)

Start in base 10:

6 +' -19


Convert to base -2:

11010 +' 10111


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


Convert your result back into base 10:

-3


## XOR multiplication in Base -2

Once again XOR multiplication in base -2 is nearly the same as XOR multiplication in binary. If you are not familiar with XOR multiplication in base 2 there is an excellent explanation here I suggest you take a look at that first.

XOR multiplication in Base -2 is the same as performing long multiplication in base -2 except when it comes to the last step instead of adding up all of the numbers with a traditional + you use the +' we defined above.

Here is an example worked out below:

Start in decimal:

8 *' 7


Convert to Base -2:

11000 *' 11011


Set up long division:

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


Multiply the first number by every place in the second

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


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


Convert the result back to decimal:

280


# The challenge

Your challenge is to verify whether or not a number is an XOR prime in base -2. A number is an XOR prime in base -2 if the only pair of integers that multiply to it in base are 1 and itself. (1 is not prime)

You will take in a number and output a boolean, truthy if the input is an XOR prime in base -2 falsy otherwise.

Solutions will be scored in bytes with attaining the lowest number of bytes as the goal.

# Test cases

The following are all XOR primes in base -2:

-395
-3
-2
3
15
83


The following are not XOR primes in base -2:

-500
-4
0
1
258
280

• 258 seems to equal -2 *' -129 = 10 *' 10000011 – JungHwan Min Jan 14 '17 at 3:46
• @JungHwanMin my bad that one was supposed to be in the other category. I apologize if this has caused you any trouble. – Wheat Wizard Jan 14 '17 at 3:58

# Mathematica, 156 101 bytes

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


As stated here, this works because XOR multiplication is essentially multiplication in the polynomial ring F_2.

Explanation

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


Start with {input}. Repeatedly replace a number a (except 0 and 1) by a mod 2 and prepend -floor(a/2), until it does not change. This calculates the input in base -2.

FromDigits[ ... ,x]


Create a polynomial using the digits of the base -2 number, using x as the variable. e.g. {1, 1, 0} -> x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]


Check whether the resulting polynomial is irreducible, with modulus 2.

Old version (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~#&


List of primes

Here's a list of base -2 XOR primes between -1000 and 1000 (pastebin)