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

Add them without carrying:

   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

Add up all the results using base -2 XOR addition

       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. – Post Left Garf Hunter 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)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.