Was ist eine Hälfte auf der Uhr?

25

In meinem Zimmer habe ich diese witzige Uhr (zum Vergrößern anklicken):

Bildbeschreibung hier eingeben

Die meisten davon sind nicht schwer herauszufinden, aber die für 4 Uhr ist besonders schwierig:

zwei hoch negativ eins modulo sieben

Normalerweise ist ein Bruch wie 1/2 in der modularen Arithmetik nicht sinnvoll, da nur ganze Zahlen beteiligt sind. Der richtige Weg ist also, dies als die Umkehrung von 2 zu sehen, oder anders ausgedrückt, zwei hoch eins negativist diese Zahl, xbei der zweimal x ist eins. Auf diese Weise ausgedrückt, wird ein Moment des Nachdenkens dies offenbaren, x ist gleich vierweil zwei x gleich zwei mal vier gleich acht, was einem Modulo sieben entspricht.

Es wäre jedoch viel zu einfach, die multiplikative Inverse zu finden. Lassen Sie uns also die Schwierigkeit der Exponentiation erhöhen, oder mit anderen Worten den modularen Logarithmus oder den diskreten Logarithmus von 2 finden. In diesem Fall ist 3 der modulare Logarithmus von 2 in Bezug auf 7. Für diejenigen von Ihnen mit Zahlentheorie / abstrakter Algebra Hintergrund bedeutet dies, die multiplikative Ordnung von 2 Modulo n zu berechnen.

Die Herausforderung

Bei einer positiven ungeraden Ganzzahl ngrößer als 1 wird die kleinste positive Ganzzahl ausgegeben, xbei der Bildbeschreibung hier eingeben.

Beispiele

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
quelle
3
@ CᴏɴᴏʀO'Bʀɪᴇɴ: Das ist nur binär.
El'endia Starman
2
Grafische Eingabe!
Conor O'Brien
6
x^-1bedeutet multiplikative Inverse von x , dh die Zahl y, so dass xy = 1 ist . Im Feld der reellen Zahlen ist 2 ^ -1 = 0,5 . Im Ring der ganzen Zahlen modulo 7 ist 2 ^ -1 = 4 .
Dennis
4
Modulare Arithmetik ist komisch.
SuperJedi224
3
@ SuperJedi224 Modulare Arithmetik ist komisch, und trotzdem machst du es wahrscheinlich mindestens einmal am Tag, ohne es zu merken. Wenn Sie 12 Stunden verwenden und jemand Sie bittet, sie in zwei Stunden anzurufen, und es ist 11:00 Uhr, und Sie beschließen, sie um 1:00 Uhr anzurufen, haben Sie nur modulare Arithmetik ausgeführt. Ich finde es gut, dass eine der Zahlen auf dieser Uhr auf eine Weise ausgedrückt wird, die manchmal als "Uhrarithmetik" bezeichnet wird.
Todd Wilcox

Antworten:

17

Gelee , 6 Bytes

R2*%i1

Probieren Sie es online!

Wie es funktioniert

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
quelle
13

Pyth - 9 8 Bytes

f!t.^2TQ

Test Suite .

fFilter vom Standardwert 1 bis zum Auffinden von x, sodass die modulare Exponentiation mit 2 und der Eingabe gleich 1 ist.

Maltysen
quelle
11

Python, 32 Bytes

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

Beginnend mit 2, verdoppelt modulo n, bis das Ergebnis 1 ist, inkrementiert jedes Mal rekursiv und endet mit einer Zählung von 1 für den Anfangswert von 2.

xnor
quelle
8

Mathematica, 24 Bytes

2~MultiplicativeOrder~#&

Ich habe nur ein eingebautes dafür verwendet.

LegionMammal978
quelle
20
Natürlich hat Mathematica dafür eine eingebaute. : P
El'endia Starman
7
@ El'endiaStarman Natürlich hat Mathematica eine unrühmliche eingebaut. : - {D
wizzwizz4
7

APL, 8 Bytes

1⍳⍨⊢|2*⍳

Dies ist ein monadischer Funktionszug, der eine Ganzzahl rechts akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Erklärung (Aufruf der Eingabe 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

Beachten Sie, dass das Ergebnis bei großen Eingaben möglicherweise falsch ist, da das Exponential gerundet wird.

Alex A.
quelle
1
Auch 8: ⍴∘∪⊢|2*⍳.
Lirtosiast
6

Pyth, 14 Bytes

VQIq%^2hNQ1hNB

Erläuterung:

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

Probieren Sie es hier aus

Adnan
quelle
Ich bekomme 66\n132\n198für eine Eingabe von 201.
El'endia Starman
@ El'endiaStarman Entschuldigung, falscher Link: p
Adnan
Oh, haha, jetzt ist es gut. :)
El'endia Starman
5

JavaScript (ES6), 28 Byte

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

Basierend auf @ xnors brillantem rekursiven Ansatz.

ETHproductions
quelle
Hast du einen Link, unter dem ich das testen kann? Scheint in der Konsole unter Chrome nicht zu funktionieren. (SyntaxError aufgrund =>, denke ich.)
El'endia Starman
@ El'endiaStarman Hier gehts. .
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ: Ich kann nicht herausfinden, wie ich es testen soll.
El'endia Starman
@ El'endiaStarman Dieser Code hat eine Funktion definiert, die wie folgt aufgerufen werden kann f(3). Aus irgendeinem blöden Grund können Sie diese Funktion auf dieser Website nur verwenden, wenn Sie sie mit letoder deklarieren var. Versuche dies.
ETHproductions
1
@Pavlo Ich weiß, dass Lambdas akzeptiert werden, aber diese Funktion muss benannt werden, damit sie sich selbst aufrufen kann. Ich werde einen Test-Suite-Link hinzufügen, wenn ich wieder auf meinem Computer bin.
ETHproductions
5

05AB1E , 11 Bytes

Code:

DUG2NmX%iNq

Erläuterung:

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
quelle
5

Julia, 25 24 Bytes

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

Dies ist einfach - 2.^(1:n)%nfindet die Potenzen von 2 innerhalb der Menge, dient unionaber als uniqueund gibt nur eine von jeder eindeutigen Potenz zurück (und da es sich um einen Infix-Operator handelt, kann ich eine Vereinigung mit 1 herstellen, um ein Byte über den ∪(2.^(1:n)%n)Ansatz zu speichern ). Dann endofzählt die Anzahl der einzigartigen Kräfte, denn wenn es 1 trifft, wird es nur die vorhandenen Kräfte wiederholen, so dass es so viele eindeutige Werte als die Kraft , die 1 erzeugt sein werden.

Glen O
quelle
5

Im Ernst, 14 Bytes

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

Hex Dump:

312c3bbb5260d3bd4025604da175

Probieren Sie es online

Erläuterung:

 ,;╗           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.
Quintopie
quelle
4

Haskell, 30 Bytes

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

Das Hilfsargument twird modulo für njeden Schritt verdoppelt, bis es 1 entspricht.

xnor
quelle
Wie könnte ich das testen?
El'endia Starman
Siehe hier
Lynn
@ Mauris: Danke!
El'endia Starman
2

Japt, 17 Bytes

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

Probieren Sie es online!

Dies wäre drei Bytes kürzer, wenn Japt die Funktion "Finde das erste Objekt, das dieser Bedingung entspricht" hätte. Startet die Arbeit an einem

Wie es funktioniert

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
ETHproductions
quelle
2

PARI / GP, 20 Bytes

n->znorder(Mod(2,n))
Alephalpha
quelle
2

Julia, 33 26 Bytes

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

Dies ist eine Lambda-Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Wir konstruieren ein Array als 2, die auf jede ganzzahlige Potenz von 1 bis erhöht wird n , und finden dann den Index der ersten 1 in diesem Array.

7 Bytes gespart dank Glen O!

Alex A.
quelle
Der Befehl map ist nicht erforderlich 2.^(1:n)%n. Verwenden Sie einfach .
Glen O
@ GlenO Das funktioniert perfekt, danke!
Alex A.
2

MATL , 13 Bytes

it:Hw^w\1=f1)

Läuft auf Octave mit dem aktuellen GitHub-Commit des Compilers.

Funktioniert für Eingaben bis 51(aufgrund von Einschränkungen derdouble Datentyps).

Beispiel

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

Erläuterung

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
quelle
2

Unicorn , 1307 1062 976 Bytes

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

Ich versuche, Einhorn zu einer ernsthaften Golfsprache zu machen, aber das ist ein bisschen schwierig ...

Hoffentlich finde ich einen Weg, die "Einhornigkeit" der Sprache beizubehalten und gleichzeitig viel weniger Bytes zu erzeugen


Bild:

Bildbeschreibung hier eingeben

Verwendet eine benutzerdefinierte Codierung.

Diese Antwort ist nicht konkurrierend, da sie eine Version von Unicorn verwendet, die nach dieser Sprache erstellt wurde

Doᴡɴɢᴏᴀᴛ
quelle
3
Die Regenbogen und Einhörner sind stark mit diesem ...
Mama Fun Roll
Jemand hat sich UnicornRLE ausgedacht
Sebi
Bin ich der einzige, ((2)2(2))(())der mit dem @ Downgoat-Interpreter aus dem Code herauskommt?
18.
2

𝔼𝕊𝕄𝕚𝕟 11 Zeichen / 22 Bytes

↻2ⁿḁ%ï>1)⧺ḁ

Try it here (Firefox only).

Verwendet eine while-Schleife. Dies ist einer der wenigen Fälle, in denen eine while-Schleife besser ist als die Zuordnung über einen Bereich.

Erläuterung

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

CJam, 15 Bytes

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

Peter Taylor hat ein Byte gespeichert. Ordentlich!

Lynn
quelle
Anstatt 1fe|du könntest :)und dann )nachdem du das getan hast #.
Peter Taylor
2qi,:)f#_,f%1#)
Peter Taylor
Natürlich. Vielen Dank.
Lynn
0

Prolog, 55 Bytes

Code:

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

Erklärt:

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

Beispiel:

p(195).
12

Probieren Sie es hier online aus

Emigna
quelle