Il y a environ un an, on vous a demandé de trouver les nombres premiers XOR . Ce sont des nombres dont les seuls facteurs sont 1 et eux-mêmes lors de la multiplication XOR en base 2 . Maintenant, nous allons pimenter un peu les choses.

Nous allons trouver les nombres premiers XOR en base -2

Conversion en base -2

La base -2 ressemble beaucoup à toutes les autres bases. La place la plus à gauche est la place 1s (1 = (-2) ⁰ ), à côté de la place -2s (-2 = (-2) ¹ ), à côté de la place 4s (4 = (-2 ) ² ), et ainsi de suite. La grande différence est que les nombres négatifs peuvent être représentés en base -2 sans signe négatif.

Voici quelques exemples de conversions:

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

Ajout de XOR dans Base -2

L'addition XOR en Base -2 est à peu près la même que l'addition XOR en binaire. Vous convertissez simplement le nombre en Base -2 et XOR chaque chiffre en place. (C'est la même chose que l'ajout sans le portage)

Voici un exemple travaillé étape par étape:

(Nous utiliserons le symbole +'pour indiquer l'addition XOR Base -2)

Départ en base 10:

6 +' -19

Convertir en base -2:

11010 +' 10111

Ajoutez-les sans porter:

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

Convertissez votre résultat en base 10:

-3

Multiplication XOR en Base -2

Une fois de plus, la multiplication XOR en base -2 est presque la même que la multiplication XOR en binaire. Si vous n'êtes pas familier avec la multiplication XOR en base 2, il y a une excellente explication ici, je vous suggère de jeter un œil à cela en premier.

La multiplication XOR en Base -2 est la même que la multiplication longue en base -2 sauf quand il s'agit de la dernière étape au lieu de additionner tous les nombres avec un traditionnel que +vous utilisez celui que +'nous avons défini ci-dessus.

Voici un exemple élaboré ci-dessous:

Commencez en décimal:

8 *' 7

Convertir en base -2:

11000 *' 11011

Mettre en place une division longue:

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

Multipliez le premier nombre par chaque place dans le second

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

Additionnez tous les résultats en utilisant l'addition XOR base -2

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

Convertissez le résultat en décimal:

280

Le défi

Votre défi consiste à vérifier si un nombre est ou non un nombre XOR premier en base -2. Un nombre est un nombre XOR premier en base -2 si la seule paire d'entiers qui s'y multiplient en base est 1 et lui-même. (1 n'est pas premier)

Vous prendrez un nombre et sortirez un booléen, véridique si l'entrée est un nombre XOR premier en base -2 sinon.

Les solutions seront notées en octets avec comme objectif d'atteindre le plus petit nombre d'octets.

Cas de test

Les éléments suivants sont tous des nombres premiers XOR en base -2:

-395
-3
-2
 3
 15
 83

Les éléments suivants ne sont pas des nombres premiers XOR en base -2:

-500
-4
 0
 1
 258
 280

Mathematica, 156 101 octets

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

Comme indiqué ici , cela fonctionne parce que la multiplication XOR est essentiellement une multiplication dans l'anneau polynomial F_2.

Explication

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

Commencez par {input}. Remplacez à plusieurs reprises un nombre a(sauf 0 et 1) par le amod 2 et ajoutez -floor ( a/ 2), jusqu'à ce qu'il ne change pas. Ceci calcule l'entrée en base -2.

FromDigits[ ... ,x]

Créez un polynôme en utilisant les chiffres du nombre de base -2, en utilisant xcomme variable. par exemple {1, 1, 0}->x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]

Vérifiez si le polynôme résultant est irréductible, avec le module 2.

Ancienne version (156 octets)

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

Liste des nombres premiers

Voici une liste de nombres premiers XOR de base -2 entre -1000 et 1000 (pastebin)