W moim pokoju mam ten naukowy zegar (kliknij, żeby zobaczyć pełny rozmiar):
Większość z nich nie jest trudna do odgadnięcia, ale ta z 4-godzinnym zegarem jest szczególnie trudna:
Zwykle ułamek taki jak 1/2 nie ma sensu w arytmetyce modułowej, ponieważ w grę wchodzą tylko liczby całkowite. Prawidłowym sposobem jest zatem postrzeganie tego jako odwrotności liczby 2 lub, mówiąc inaczej, to ta liczba gdzie . Mówiąc w ten sposób, chwilowa myśl ujawni to, ponieważ .
Jednak samo znalezienie odwrotności multiplikatywnej byłoby zdecydowanie zbyt łatwe jako wyzwanie. Podkreślmy więc trudność z potęgowaniem, czyli innymi słowy, znalezienie logarytmu modularnego lub logarytmu dyskretnego 2. W tym przypadku 3 jest logarytmem modularnym 2 w odniesieniu do 7. Dla tych z was, którzy mają teorię liczb / algebrę abstrakcyjną tło, oznacza to obliczenie mnożnika rzędu 2 modułów.
Wyzwanie
Biorąc pod uwagę dodatnią nieparzystą liczbę całkowitą n
większą niż 1, wypisuje najmniejszą dodatnią liczbę całkowitą x
gdzie .
Przykłady
n x
3 2
5 4
7 3
9 6
11 10
13 12
15 4
17 8
19 18
21 6
23 11
25 20
27 18
29 28
31 5
33 10
35 12
37 36
39 12
41 20
43 14
45 12
47 23
49 21
51 8
53 52
55 20
57 18
59 58
61 60
63 6
65 12
67 66
69 22
71 35
73 9
75 20
77 30
79 39
81 54
83 82
85 8
87 28
89 11
91 12
93 10
95 36
97 48
99 30
101 100
103 51
105 12
107 106
109 36
111 36
113 28
115 44
117 12
119 24
121 110
123 20
125 100
127 7
129 14
131 130
133 18
135 36
137 68
139 138
141 46
143 60
145 28
147 42
149 148
151 15
153 24
155 20
157 52
159 52
161 33
163 162
165 20
167 83
169 156
171 18
173 172
175 60
177 58
179 178
181 180
183 60
185 36
187 40
189 18
191 95
193 96
195 12
197 196
199 99
201 66
źródło
x^-1
oznacza multiplikatywną odwrotność x , tj. liczbę y taką, że xy = 1 . W zakresie liczb rzeczywistych 2 ^ -1 = 0,5 . W pierścieniu liczb całkowitych modulo 7 , 2 ^ -1 = 4 .Odpowiedzi:
Galaretka , 6 bajtów
Wypróbuj online!
Jak to działa
źródło
Pyth -
98 bajtówPakiet testowy .
f
ilters od domyślnej 1, aż znajdzie jakieś x, tak że wykładnik modułowy z 2 i wejście równa się 1.źródło
Python, 32 bajty
Począwszy od 2, podwaja moduł aż do wyniku 1, za każdym razem rekurencyjnie zwiększając, a kończąc na liczbie 1 dla wartości początkowej 2.
źródło
Mathematica, 24 bajty
Po prostu użyłem do tego wbudowanego.
źródło
APL, 8 bajtów
Jest to monadyczny ciąg funkcji, który przyjmuje liczbę całkowitą po prawej stronie i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.
Objaśnienie (wywołanie wejścia
x
):Zauważ, że wynik może być niepoprawny dla dużych danych wejściowych, ponieważ wykładnicza zostaje zaokrąglona.
źródło
⍴∘∪⊢|2*⍳
.Pyth, 14 bajtów
Wyjaśnienie:
Wypróbuj tutaj
źródło
66\n132\n198
za wkład201
.JavaScript (ES6), 28 bajtów
Oparty na genialnym rekurencyjnym podejściu @ xnor.
źródło
=>
mi się, że występujef(3)
. Z jakiegoś głupiego powodu ta strona internetowa nie pozwoli ci korzystać z tej funkcji, chyba że zadeklarujesz ją za pomocąlet
lubvar
. Spróbuj tego.05AB1E , 11 bajtów
Kod:
Wyjaśnienie:
źródło
Julia,
2524 bajtówJest to proste -
2.^(1:n)%n
znajduje potęgi 2 w zestawie,∪
jestunion
, ale służyunique
i zwraca tylko jedną z każdej unikalnej mocy (a ponieważ jest to operator infix, mogę połączyć się z 1, aby zaoszczędzić bajt nad∪(2.^(1:n)%n)
podejściem). Następnieendof
liczy liczbę unikalnych mocy, ponieważ gdy osiągnie 1, po prostu powtórzy istniejące moce, więc będzie tyle unikalnych wartości, co moc, która daje 1.źródło
Poważnie, 14 bajtów
Hex Dump:
Wypróbuj online
Wyjaśnienie:
źródło
Haskell, 30 bajtów
Argument pomocnika
t
jest podwojony modulo nan
każdym kroku, aż będzie równy 1.źródło
Japt, 17 bajtów
Wypróbuj online!
Byłoby to trzy bajty krótsze, gdyby Japt miał funkcję „znajdź pierwszy element, który spełnia ten warunek”. Rozpoczyna pracę nad jednym
Jak to działa
źródło
PARI / GP, 20 bajtów
źródło
Julia,
3326 bajtówJest to funkcja lambda, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.
Konstruujemy tablicę jako 2 podniesioną do każdej liczby całkowitej od 1 do
n
, a następnie znajdujemy indeks pierwszej 1 w tej tablicy.Zaoszczędź 7 bajtów dzięki Glen O!
źródło
2.^(1:n)%n
.Perl 5, 29 bajtów
Czapka z daszkiem.
źródło
MATL , 13 bajtów
Działa na Octave z bieżącym zatwierdzeniem GitHub kompilatora.
Działa dla danych wejściowych do
51
(z powodu ograniczeńdouble
typu danych).Przykład
Wyjaśnienie
źródło
Jednorożec ,
1307 1062976 bajtówPróbuję uczynić jednorożca poważnym językiem golfa, ale to trochę trudne ...
Mam nadzieję, że znajdę sposób, aby zachować „jednorożec-ności” w języku jednocześnie znacznie mniej bajtów
Obrazek:
Używa niestandardowego kodowania.
Ta odpowiedź nie jest konkurencyjna, ponieważ wykorzystuje wersję Unicorn wykonaną po tym języku
źródło
((2)2(2))(())
wychodzę z kodu dzięki tłumaczowi @ Downgoat?𝔼𝕊𝕄𝕚𝕟, 11 znaków / 22 bajty
Try it here (Firefox only).
Wykorzystuje pętlę while. Jest to jedna z niewielu razy, gdy pętla while jest lepsza niż mapowanie w zakresie.
Wyjaśnienie
źródło
CJam, 15 bajtów
Peter Taylor uratował bajt. Schludny!
źródło
1fe|
mogłeś:)
a następnie)
po wykonaniu#
.2qi,:)f#_,f%1#)
Prolog, 55 bajtów
Kod:
Wyjaśnił:
Przykład:
Wypróbuj online tutaj
źródło