What's a half on the clock?

In my room, I have this geeky clock (click for full size): Most of these are not difficult to figure out, but the one for 4-o-clock is particularly tricky: Normally, a fraction like 1/2 doesn't make sense in modular arithmetic since only integers are involved. The correct way, then, is to see this as the inverse of 2, or to put it another way, is that number where . Put this way, a moment's thought will reveal that because .

However, simply finding the multiplicative inverse would be far too easy as a challenge. So let's bump up the difficulty to exponentiation, or in other words, finding the modular logarithm or discrete logarithm of 2. In this case, 3 is the modular logarithm of 2 with respect to 7. For those of you with number theory/abstract algebra background, this means calculating the multiplicative order of 2 modulo n.

The Challenge

Given a positive odd integer n greater than 1, output the smallest positive integer x where .

Examples

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
• @CᴏɴᴏʀO'Bʀɪᴇɴ: That's just binary. Dec 29 '15 at 0:18
• Graphical input! Dec 29 '15 at 0:19
• x^-1 means multiplicative inverse of x, i.e., the number y such that xy = 1. In the field of real numbers, 2^-1 = 0.5. In the ring of integers modulo 7, 2^-1 = 4. Dec 29 '15 at 16:15
• Modular arithmetic is weird. Dec 29 '15 at 16:28
• @SuperJedi224 Modular arithmetic is weird, and yet you probably do it at least once a day without realizing it. If you use 12 hour time, and someone asks you to call them in two hours, and it's 11:00 and you decide to call them at 1:00, you just did modular arithmetic. I find it neat that one of the numbers on this clock is expressed in a way that is sometimes called "clock arithmetic". Dec 29 '15 at 18:17

Jelly, 6 bytes

R2*%i1

Try it online!

How it works

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.

Pyth - 9 8 bytes

f!t.^2TQ

filters from default of 1 till it finds some x such that modular exponentiation with 2 and the input equals 1.

Python, 32 bytes

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

Starting with 2, doubles modulo n until the result is 1, recursively incrementing each time, and ending with a count of 1 for the initial value of 2.

Mathematica, 24 bytes

2~MultiplicativeOrder~#&

I just used a built-in for this.

• Of course Mathematica has a built-in for this. :P Dec 29 '15 at 1:13
• @El'endiaStarman Of course Mathematica has an ungolfable built-in for this. :-{D Dec 29 '15 at 18:08

APL, 8 bytes

1⍳⍨⊢|2*⍳

This is a monadic function train that accepts an integer on the right and returns an integer. To call it, assign it to a variable.

Explanation (calling the input 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

Note that the result may be incorrect for large inputs since the exponential gets rounded.

• Also 8: ⍴∘∪⊢|2*⍳. Dec 30 '15 at 2:41

Pyth, 14 bytes

VQIq%^2hNQ1hNB

Explanation:

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

Try it here

• I get 66\n132\n198 for an input of 201. Dec 28 '15 at 23:17
• @El'endiaStarman sorry, wrong link :p Dec 28 '15 at 23:18
• Oh, haha, it's good now. :) Dec 28 '15 at 23:19

JavaScript (ES6), 28 bytes

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

Based on @xnor's brilliant recursive approach.

• Do you have a link I can test this at? Doesn't seem to work in the console on Chrome. (SyntaxError due to =>, I think.) Dec 28 '15 at 23:21
• @El'endiaStarman Here ya go.. Dec 28 '15 at 23:43
• @CᴏɴᴏʀO'Bʀɪᴇɴ: I can't figure out how to test it. Dec 29 '15 at 0:21
• @El'endiaStarman This code defined a function which can be called like f(3). For some stupid reason, that website won't let you use this function unless you declare it with let or var. Try this. Dec 29 '15 at 0:26
• @Pavlo I know lambdas are accepted, but this function needs to be named so it can call itself. I'll add a test suite link when I get back to my computer. Dec 29 '15 at 13:31

05AB1E, 11 bytes

Code:

DUG2NmX%iNq

Explanation:

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
• 10 bytes Mar 15 '20 at 14:08

Julia, 25 24 bytes

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

This is simple - 2.^(1:n)%n finds the powers of 2 within the set, is union, but serves as unique and returns only one of each unique power (and because it's an infix operator, I can union with 1 to save a byte over the ∪(2.^(1:n)%n) approach). Then endof counts the number of unique powers, because once it hits 1, it'll just repeat the existing powers, so there'll be as many unique values as the power that produces 1.

Seriously, 14 bytes

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

Hex Dump:

312c3bbb5260d3bd4025604da175

Try It Online

Explanation:

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

n%1=1
n%t=1+n%(2*tmodn)
(%2)

Helper argument t is doubled modulo n each step until it equals 1.

• How might I test this? Dec 29 '15 at 1:12
• See here
– Lynn
Dec 29 '15 at 1:38
• @Mauris: Thanks! Dec 29 '15 at 1:50

Japt, 17 bytes

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

Try it online!

This would be three bytes shorter if Japt had a "find the first item that matches this condition" function. Starts work on one

How it works

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

PARI/GP, 20 bytes

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

Julia, 33 26 bytes

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

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

We construct an array as 2 raised to each integer power from 1 to n, then we find the index of the first 1 in this array.

Saved 7 bytes thanks to Glen O!

• No need for the map command, just use 2.^(1:n)%n. Dec 29 '15 at 4:59
• @GlenO That works perfectly, thanks! Dec 29 '15 at 5:03

Perl 5, 29 bytes

$n=<>;{2**++$_%\$n-1?redo:say}

Hat tip.

MATL, 13 bytes

it:Hw^w\1=f1)

Runs on Octave with the current GitHub commit of the compiler.

Works for input up to 51 (due to limitations of the double data type).

Example

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

Explanation

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

Unicorn, 1307 1062 976 bytes

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

I'm attempting to make unicorn a serious golfing language but that's a bit difficult...

Hopefully I'll find a way to retain the "unicorn-ness" of the language while making much less bytes

Picture: Uses a custom encoding.

This answer is non-competing because it uses a version of Unicorn made after this language

• The rainbows and unicorns are strong with this one... Dec 30 '15 at 2:21
• Somebody come up with UnicornRLE
– Sebi
Dec 31 '15 at 15:36
• Am I the only one getting ((2)2(2))(()) out of the code with @Downgoat's interpreter? Jan 18 '16 at 23:13

𝔼𝕊𝕄𝕚𝕟, 11 chars / 22 bytes

↻2ⁿḁ%ï>1)⧺ḁ

Try it here (Firefox only).

Uses a while loop. This is one of the few times a while loop is better than mapping over a range.

Explanation

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

CJam, 15 bytes

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

Peter Taylor saved a byte. Neat!

• Rather than 1fe| you could :) and then ) after doing the #. Dec 30 '15 at 10:22
• 2qi,:)f#_,f%1#) Dec 30 '15 at 12:08
• Ohh, of course. Thank you.
– Lynn
Dec 30 '15 at 12:19

Prolog, 55 bytes

Code:

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

Explained:

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

Example:

p(195).
12

Try it online here

Try it

Python 3, 37 bytes

f=lambda n,x=1:2**x%n==1or 1+f(n,x+1)

Try it online!

Thanks Maria Miller for saving me 1 byte.

• 37 bytes Mar 15 '20 at 14:13

C (gcc), 35 bytes

i;f(n){for(i=1;(1<<i++)%n-1;);--i;}

Gives accurate results up to $$\x=31\$$, otherwise the result is 32.

Try it online!