# 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. – Ad Hoc Garf Hunter Jan 14 '17 at 3:58
• In your addition example 6 +' -19 you actually use 19 not -19. – J42161217 Jul 13 at 18:47

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

# APL (Dyalog Extended), 36 bytes

{2=≢⍸⍵=∘.{¯2⊥≠/⊤⍺×2*⍸⌽⊤⍵}⍨1+⍳8×1+|⍵}


Try it online!

Simple brute-force, and extremely inefficient (input 15 takes ~1s). Given an integer n, it generates a range large enough that their binary representation evaluated in negabinary includes n, evaluates its multiplication table (last step evaluated to negabinary instead of binary), then checks if the input appears exactly twice.

The algorithm was inspired by a solution to regular XOR primes.

### How it works

{2=≢⍸⍵=∘.{¯2⊥≠/⊤⍺×2*⍸⌽⊤⍵}⍨1+⍳8×1+|⍵}  ⍝ Inline function; ⍵←n
8×1+|⍵   ⍝ 8×(1+abs(n))
1+⍳         ⍝ 1-based range of above
∘.{              }⍨  ⍝ Evaluate XORmul table
⊤⍵    ⍝ Binary of right arg
2*⍸⌽      ⍝ Digit values of ones
⊤⍺×          ⍝ Multiply left arg and convert each to binary
≠/             ⍝ Digit-wise XOR
¯2⊥               ⍝ Interpret as negabinary and convert to integer
2=≢⍸⍵=  ⍝ Does n appear exactly twice in the table?