Около года назад вас попросили найти простые числа XOR . Это числа, чьи единственные факторы равны 1 и сами при выполнении умножения XOR в базе 2 . Теперь были немного оживлены.

Мы собираемся найти простые числа XOR в базе -2

Преобразование в базу -2

База -2 очень похожа на любую другую базу. Самое левое место - это 1-е место (1 = (-2) ⁰ ), рядом с ним - -2-е место (-2 = (-2) ¹ ), рядом - 4-е место (4 = (-2) ) ² ) и тд и тп. Большая разница в том, что отрицательные числа могут быть представлены в базе -2 без каких-либо отрицательных знаков.

Вот несколько примеров конверсий:

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

Добавление XOR в базу -2

Добавление XOR в Base-2 во многом аналогично добавлению XOR в двоичном виде. Вы просто конвертируете число в Base -2 и XOR каждой цифры на месте. (Это то же самое, что и сложение без переноса)

Вот пример, проработанный шаг за шагом:

(Мы будем использовать символ +'для обозначения добавления базы XOR X)

Начните с базы 10:

6 +' -19

Преобразовать в базу -2:

11010 +' 10111

Добавьте их без ношения:

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

Преобразуйте ваш результат обратно в базу 10:

-3

Умножение XOR в Base -2

Еще раз умножение XOR в базе -2 почти такое же, как умножение XOR в двоичном виде. Если вы не знакомы с XOR умножения в базе 2 есть отличное объяснение здесь я предлагаю вам взглянуть на это первое.

Умножение XOR в Base-2 - это то же самое, что и длинное умножение в Base-2, за исключением того, что когда дело доходит до последнего шага, вместо сложения всех чисел с традиционным +, используемым вами, как +'мы определили выше.

Вот пример, разработанный ниже:

Начать в десятичном формате:

8 *' 7

Преобразовать в базу -2:

11000 *' 11011

Установить длинное деление:

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

Умножьте первое число на каждое место во втором

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

Сложите все результаты, используя базовое добавление XOR

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

Преобразуйте результат обратно в десятичное число:

280

Соревнование

Ваша задача - проверить, является ли число простым XOR в базе -2. Число - это простое число XOR в базе -2, если единственной парой целых чисел, умножающихся на него в базе, являются 1 и сама. (1 не простое)

Вы возьмете число и выведите логическое значение, правда, если в противном случае вводом является простое число XOR в базе -2.

Решения будут оцениваться в байтах с достижением наименьшего количества байтов в качестве цели.

Контрольные примеры

Ниже приведены все простые числа XOR в базе -2:

-395
-3
-2
 3
 15
 83

Следующие числа не являются простыми числами XOR в базе -2:

-500
-4
 0
 1
 258
 280

Mathematica, 156 101 байт

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

Как указано здесь , это работает, потому что умножение XOR по существу является умножением в кольце многочленов F_2.

объяснение

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

Начните с {input}. Повторно заменяйте число a(кроме 0 и 1) на amod 2 и добавляйте -floor ( a/ 2), пока оно не изменится. Это вычисляет вход в базу -2.

FromDigits[ ... ,x]

Создайте полином, используя цифры базового числа -2, используя xв качестве переменной. например {1, 1, 0}->x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]

Проверьте, является ли полученный многочлен неприводимым, с модулем 2.

Старая версия (156 байт)

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~#&

Список простых чисел

Вот список базовых -2 простых чисел XOR между -1000 и 1000 (pastebin)