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) 0 ), obok to miejsce -2s (-2 = (-2) 1 ), obok to miejsce 4s (4 = (-2) ) 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
źródło
258
wydaje się równy-2 *' -129 = 10 *' 10000011
Odpowiedzi:
Mathematica,
156101 bajtówJak stwierdzono tutaj , działa to, ponieważ mnożenie XOR jest zasadniczo zwielokrotnieniem w pierścieniu wielomianowym F_2.
Wyjaśnienie
Zacznij od
{input}
. Kilkakrotnie zamień liczbęa
(oprócz 0 i 1) naa
mod 2 i dodaj -floor (a
/ 2), aż się nie zmieni. Oblicza to dane wejściowe w bazie -2.Utwórz wielomian za pomocą cyfr liczby podstawowej -2, używając
x
jako zmiennej. np.{1, 1, 0}
->x^2 + x
Sprawdź, czy wynikowy wielomian jest nieredukowalny, z modułem 2.
Stara wersja (156 bajtów)
Lista liczb pierwszych
Oto lista bazowych liczb pierwszych -2 XOR od -1000 do 1000 (pastebin)
źródło