Co jest w połowie na zegarze?

25

W moim pokoju mam ten naukowy zegar (kliknij, żeby zobaczyć pełny rozmiar):

wprowadź opis zdjęcia tutaj

Większość z nich nie jest trudna do odgadnięcia, ale ta z 4-godzinnym zegarem jest szczególnie trudna:

dwa do potęgi jednego ujemnego modulo siedem

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, dwa do potęgi negatywnejto ta liczba xgdzie dwa razy x równa się jeden. Mówiąc w ten sposób, chwilowa myśl ujawni to, x równa się czteryponieważ dwa x równa się dwa razy cztery równa się osiem, co odpowiada jednemu modułowi siódmemu.

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ą nwiększą niż 1, wypisuje najmniejszą dodatnią liczbę całkowitą xgdzie wprowadź opis zdjęcia tutaj.

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 
El'endia Starman
źródło
3
@ CᴏɴᴏʀO'Bʀɪᴇɴ: To tylko binarne.
El'endia Starman
2
Wprowadzanie graficzne!
Conor O'Brien
6
x^-1oznacza 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 .
Dennis
4
Arytmetyka modułowa jest dziwna.
SuperJedi224,
3
@ SuperJedi224 Arytmetyka modułowa jest dziwna, a jednak prawdopodobnie robisz to przynajmniej raz dziennie, nie zdając sobie z tego sprawy. Jeśli wykorzystasz czas 12 godzin, a ktoś poprosi cię o telefon w ciągu dwóch godzin, a jest godzina 11:00, a ty zdecydujesz się zadzwonić o godzinie 1:00, właśnie wykonałeś arytmetykę modułową. Uważam, że to fajne, że jedna z liczb na tym zegarze jest wyrażana w sposób, który jest czasami nazywany „arytmetyką zegara”.
Todd Wilcox,

Odpowiedzi:

17

Galaretka , 6 bajtów

R2*%i1

Wypróbuj online!

Jak to działa

R2*%i1  Input: n

R       Range; yield [1, ..., n].
 2*     Compute [2**1, ..., 2**n].
   %    Hook; take all powers modulo n.
    i1  Get the index of the first 1.
        Indices are 1-based, so index k corresponds to the natural number k.
Dennis
źródło
13

Pyth - 9 8 bajtów

f!t.^2TQ

Pakiet testowy .

filters od domyślnej 1, aż znajdzie jakieś x, tak że wykładnik modułowy z 2 i wejście równa się 1.

Maltysen
źródło
11

Python, 32 bajty

f=lambda n,t=2:t<2or-~f(n,2*t%n)

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.

xnor
źródło
8

Mathematica, 24 bajty

2~MultiplicativeOrder~#&

Po prostu użyłem do tego wbudowanego.

LegionMammal978
źródło
20
Od kursu Mathematica posiada wbudowany do tego. : P
El'endia Starman
7
@ El'endiaStarman Of oczywiście Mathematica posiada ungolfable wbudowaną do tego. : - {D
wizzwizz4,
7

APL, 8 bajtów

1⍳⍨⊢|2*⍳

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):

      2*⍳    ⍝ Compute 2^i for each i from 1 to x
   ⊢|        ⍝ Get each element of the resulting array modulo x
1⍳⍨          ⍝ Find the index of the first 1 in this array

Zauważ, że wynik może być niepoprawny dla dużych danych wejściowych, ponieważ wykładnicza zostaje zaokrąglona.

Alex A.
źródło
1
Również 8: ⍴∘∪⊢|2*⍳.
lirtosiast
6

Pyth, 14 bajtów

VQIq%^2hNQ1hNB

Wyjaśnienie:

VQIq%^2hNQ1hNB

                # Implicit, Q = input
VQ              # For N in range(0, Q)
  Iq      1     # If equals 1
    %^2hNQ      # 2^(N + 1) % Q
           hN   # Print (N + 1)
             B  # Break

Wypróbuj tutaj

Adnan
źródło
Dostaję 66\n132\n198za wkład 201.
El'endia Starman
@ El'endiaStarman przepraszam, zły link: p
Adnan
Och, haha, teraz jest dobrze. :)
El'endia Starman
5

JavaScript (ES6), 28 bajtów

f=(n,t=2)=>t<2||-~f(n,2*t%n)

Oparty na genialnym rekurencyjnym podejściu @ xnor.

ETHprodukcje
źródło
Czy masz link, pod którym mogę to przetestować? Wygląda na to, że nie działa w konsoli w Chrome. (Wydaje =>mi się, że występuje
błąd składniowy
@ El'endiaStarman Proszę bardzo. .
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ: Nie mogę wymyślić, jak to przetestować.
El'endia Starman
@ El'endiaStarman Ten kod definiuje funkcję, którą można wywołać podobnie f(3). Z jakiegoś głupiego powodu ta strona internetowa nie pozwoli ci korzystać z tej funkcji, chyba że zadeklarujesz ją za pomocą letlub var. Spróbuj tego.
ETHproductions
1
@Pavlo Wiem, że lambdas są akceptowane, ale ta funkcja musi zostać nazwana, aby mogła się wywoływać. Dodam link do zestawu testów, kiedy wrócę do mojego komputera.
ETHproductions
5

05AB1E , 11 bajtów

Kod:

DUG2NmX%iNq

Wyjaśnienie:

DUG2NmX%iNq

D            # Duplicates the stack, or input when empty
 U           # Assign X to last item of the stack
  G          # For N in range(1, input)
   2Nm       # Calculates 2 ** N
      X      # Pushes X
       %     # Calculates the modulo of the last two items in the stack
        i    # If equals 1 or true, do { Nq }
         N   # Pushes N on top of the stack
          q  # Terminates the program
             # Implicit, nothing has printed, so we print the last item in the stack
Adnan
źródło
5

Julia, 25 24 bajtów

n->endof(1∪2.^(1:n)%n)

Jest to proste - 2.^(1:n)%nznajduje potęgi 2 w zestawie, jest union, ale służy uniquei 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ępnie endofliczy 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.

Glen O
źródło
5

Poważnie, 14 bajtów

1,;╗R`╙╜@%`Míu

Hex Dump:

312c3bbb5260d3bd4025604da175

Wypróbuj online

Wyjaśnienie:

 ,;╗           Make 2 copies of input, put 1 in reg0
    R          push [0,1,...,n-1]
     `    `M   map the quoted function over the range
      ╙        do 2^n
       ╜@%     modulo the value in reg0
1           íu Find the 1-index of 1 in the list.
kwintopia
źródło
4

Haskell, 30 bajtów

n%1=1
n%t=1+n%(2*t`mod`n)
(%2)

Argument pomocnika tjest podwojony modulo na nkażdym kroku, aż będzie równy 1.

xnor
źródło
Jak mogę to przetestować?
El'endia Starman
Zobacz tutaj
Lynn,
@Mauris: Dzięki!
El'endia Starman
2

Japt, 17 bajtów

1oU f@2pX %U¥1} g

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

1oU f@2pX %U¥1} g   // Implicit: U = input number
1oU                 // Generate a range of numbers from 1 to U.
                    // "Uo" is one byte shorter, but the result would always be 0.
    f@        }     // Filter: keep only the items X that satisfy this condition:
      2pX %U¥1      //  2 to the power of X, mod U, is equal to 1.
                g   // Get the first item in the resulting list.
                    // Implicit: output last expression
ETHprodukcje
źródło
2

PARI / GP, 20 bajtów

n->znorder(Mod(2,n))
alephalpha
źródło
2

Julia, 33 26 bajtów

n->findfirst(2.^(1:n)%n,1)

Jest 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!

Alex A.
źródło
Nie potrzebujesz polecenia map, po prostu użyj 2.^(1:n)%n.
Glen O
@GlenO To działa idealnie, dzięki!
Alex A.,
2

MATL , 13 bajtów

it:Hw^w\1=f1)

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

>> matl it:Hw^w\1=f1)
> 17
8

Wyjaśnienie

i             % input, "N"
t:            % vector from 1 to N
Hw^           % 2 raised to that vector, element-wise
w\            % modulo N
1=            % true if it equals 1, element-wise
f1)           % index of first "true" value
Luis Mendo
źródło
2

Jednorożec , 1307 1062 976 bajtów

( ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 ( 🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 2 ) 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 ✨✨✨✨✨✨✨✨✨✨ 2 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤 ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ ( 🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 2 ✨✨✨✨✨✨✨ 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐 ) ) ( 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 ( ) )

Pró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:

wprowadź opis zdjęcia tutaj

Używa niestandardowego kodowania.

Ta odpowiedź nie jest konkurencyjna, ponieważ wykorzystuje wersję Unicorn wykonaną po tym języku

Doᴡɴɢᴏᴀᴛ
źródło
3
Tęcze i jednorożce są mocne z tym ...
Mama Fun Roll
Ktoś wymyślić UnicornRLE
Sebi
Czy tylko ja ((2)2(2))(())wychodzę z kodu dzięki tłumaczowi @ Downgoat?
Rɪᴋᴇʀ
2

𝔼𝕊𝕄𝕚𝕟, 11 znaków / 22 bajty

↻2ⁿḁ%ï>1)⧺ḁ

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

          // implicit: ï = input, ḁ = 1
↻2ⁿḁ%ï>1) // while 2 to the power of ḁ mod input is greater than 1
  ⧺ḁ      // increment ḁ
          // implicit output
Mama Fun Roll
źródło
1

CJam, 15 bajtów

2qi,:)f#_,f%1#)

Peter Taylor uratował bajt. Schludny!

Lynn
źródło
Zamiast 1fe|mogłeś :)a następnie )po wykonaniu #.
Peter Taylor,
2qi,:)f#_,f%1#)
Peter Taylor
Och, oczywiście. Dziękuję Ci.
Lynn
0

Prolog, 55 bajtów

Kod:

N*X:-powm(2,X,N)=:=1,write(X);Z is X+1,N*Z.
p(N):-N*1.

Wyjaśnił:

N*X:-powm(2,X,N)=:=1, % IF 2^X mod N == 1
     write(X)         % Print X
     ;Z is X+1,       % ELSE increase exponent X
     N*Z.             % Recurse
p(N):-N*1.            % Start testing with 2^1

Przykład:

p(195).
12

Wypróbuj online tutaj

Emigna
źródło