Negative XOR primes

9

2

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

Post Rock Garf Hunter

Posted 2017-01-13T21:10:14.930

Reputation: 55 382

258 seems to equal -2 *' -129 = 10 *' 10000011 – JungHwan Min – 2017-01-14T03:46:03.147

@JungHwanMin my bad that one was supposed to be in the other category. I apologize if this has caused you any trouble. – Post Rock Garf Hunter – 2017-01-14T03:58:07.357

Answers

3

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)

JungHwan Min

Posted 2017-01-13T21:10:14.930

Reputation: 13 290