Około rok temu zostałeś poproszony o znalezienie liczb pierwszych XOR . Są to liczby, których jedynymi czynnikami są 1 i same podczas mnożenia XOR w bazie 2 . Teraz zamierzamy trochę urozmaicić.

Znajdziemy liczby pierwsze XOR w bazie -2

Konwersja do bazy -2

Baza -2 jest podobna do każdej innej bazy. Najbardziej lewe miejsce to miejsce 1s (1 = (-2) ⁰ ), obok to miejsce -2s (-2 = (-2) ¹ ), obok to miejsce 4s (4 = (-2) ) ² ) itd. Itd. Duża różnica polega na tym, że liczby ujemne mogą być reprezentowane w podstawie -2 bez żadnego znaku ujemnego.

Oto kilka przykładowych konwersji:

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

Dodanie XOR w bazie -2

Dodatek XOR w Bazie -2 jest prawie taki sam jak dodatek XOR w wersji binarnej. Po prostu konwertujesz liczbę na Podstawę -2 i XOR każdą cyfrę na miejscu. (Jest to to samo, co dodawanie bez Carry)

Oto przykład opracowany krok po kroku:

(Użyjemy tego symbolu, +'aby wskazać dodanie podstawy -2 XOR)

Zacznij od bazy 10:

6 +' -19

Konwertuj na bazę -2:

11010 +' 10111

Dodaj je bez noszenia:

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

Przekształć swój wynik z powrotem w bazę 10:

-3

Mnożenie XOR w bazie -2

Po raz kolejny mnożenie XOR w bazie -2 jest prawie takie samo jak mnożenie XOR w systemie binarnym. Jeśli nie są zaznajomieni z XOR mnożenia w bazie 2 jest doskonały wyjaśnienie tutaj proponuję przyjrzeć się, że w pierwszej kolejności.

Mnożenie XOR w Bazie -2 jest takie samo, jak przeprowadzanie długiego mnożenia w Bazie -2, z wyjątkiem tego, że dochodzi do ostatniego kroku zamiast sumowania wszystkich liczb za pomocą tradycyjnej +metody, +'którą stosujemy powyżej.

Oto przykład opracowany poniżej:

Rozpocznij po przecinku:

8 *' 7

Konwertuj na bazę -2:

11000 *' 11011

Ustaw długi podział:

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

Pomnóż pierwszą liczbę przez każde miejsce w drugim

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

Dodaj wszystkie wyniki, dodając podstawową wartość -2 XOR

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

Konwertuj wynik z powrotem na dziesiętny:

280

Wyzwanie

Twoim wyzwaniem jest sprawdzenie, czy liczba jest liczbą pierwszą XOR w bazie -2. Liczba jest liczbą pierwszą XOR w bazie -2, jeśli jedyną parą liczb całkowitych, które mnożą się w niej w bazie, jest 1 i sama. (1 nie jest liczbą pierwszą)

Weźmiesz liczbę i wypiszesz wartość logiczną, prawdę mówiąc, jeśli wejście jest liczbą pierwszą XOR w przypadku podstawy -2-falsy, inaczej.

Rozwiązania będą punktowane w bajtach z osiągnięciem najniższej liczby bajtów jako celu.

Przypadki testowe

Oto wszystkie liczby pierwsze XOR w bazie -2:

-395
-3
-2
 3
 15
 83

Poniżej nie są liczbami pierwszymi XOR w bazie -2:

-500
-4
 0
 1
 258
 280

Mathematica, 156 101 bajtów

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

Jak stwierdzono tutaj , działa to, ponieważ mnożenie XOR jest zasadniczo zwielokrotnieniem w pierścieniu wielomianowym F_2.

Wyjaśnienie

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

Zacznij od {input}. Kilkakrotnie zamień liczbę a(oprócz 0 i 1) na amod 2 i dodaj -floor ( a/ 2), aż się nie zmieni. Oblicza to dane wejściowe w bazie -2.

FromDigits[ ... ,x]

Utwórz wielomian za pomocą cyfr liczby podstawowej -2, używając xjako zmiennej. np. {1, 1, 0}->x^2 + x

IrreduciblePolynomialQ[ ... ,Modulus->2]

Sprawdź, czy wynikowy wielomian jest nieredukowalny, z modułem 2.

Stara wersja (156 bajtów)

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

Lista liczb pierwszych

Oto lista bazowych liczb pierwszych -2 XOR od -1000 do 1000 (pastebin)