25
\$\begingroup\$

In my room, I have this geeky clock (click for full size):

enter image description here

Most of these are not difficult to figure out, but the one for 4-o-clock is particularly tricky:

two to the power of negative one modulo seven

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, two to the power of negative one is that number x where two times x equals one. Put this way, a moment's thought will reveal that x equals four because two x equals two times four equals eight which is equivalent to one modulo seven.

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 enter image description here.

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
Improve this question
\$\endgroup\$
13
  • 3
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ: That's just binary. \$\endgroup\$ Commented Dec 29, 2015 at 0:18
  • 2
    \$\begingroup\$ Graphical input! \$\endgroup\$ Commented Dec 29, 2015 at 0:19
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ Commented Dec 29, 2015 at 16:15
  • 4
    \$\begingroup\$ Modular arithmetic is weird. \$\endgroup\$ Commented Dec 29, 2015 at 16:28
  • 3
    \$\begingroup\$ @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". \$\endgroup\$ Commented Dec 29, 2015 at 18:17

23 Answers 23

Reset to default
18
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
13
\$\begingroup\$

Pyth - 9 8 bytes

f!t.^2TQ

Test Suite.

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

Improve this answer
\$\endgroup\$
11
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
9
\$\begingroup\$

Mathematica, 24 bytes

2~MultiplicativeOrder~#&

I just used a built-in for this.

Improve this answer
\$\endgroup\$
2
  • 20
    \$\begingroup\$ Of course Mathematica has a built-in for this. :P \$\endgroup\$ Commented Dec 29, 2015 at 1:13
  • 7
    \$\begingroup\$ @El'endiaStarman Of course Mathematica has an ungolfable built-in for this. :-{D \$\endgroup\$ Commented Dec 29, 2015 at 18:08
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Also 8: ⍴∘∪⊢|2*⍳. \$\endgroup\$ Commented Dec 30, 2015 at 2:41
6
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I get 66\n132\n198 for an input of 201. \$\endgroup\$ Commented Dec 28, 2015 at 23:17
  • \$\begingroup\$ @El'endiaStarman sorry, wrong link :p \$\endgroup\$ Commented Dec 28, 2015 at 23:18
  • \$\begingroup\$ Oh, haha, it's good now. :) \$\endgroup\$ Commented Dec 28, 2015 at 23:19
5
\$\begingroup\$

JavaScript (ES6), 28 bytes

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

Based on @xnor's brilliant recursive approach.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ 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.) \$\endgroup\$ Commented Dec 28, 2015 at 23:21
  • \$\begingroup\$ @El'endiaStarman Here ya go.. \$\endgroup\$ Commented Dec 28, 2015 at 23:43
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ: I can't figure out how to test it. \$\endgroup\$ Commented Dec 29, 2015 at 0:21
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 29, 2015 at 0:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 29, 2015 at 13:31
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 10 bytes \$\endgroup\$ Commented Mar 15, 2020 at 14:08
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Haskell, 30 bytes

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

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

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ How might I test this? \$\endgroup\$ Commented Dec 29, 2015 at 1:12
  • \$\begingroup\$ See here \$\endgroup\$ Commented Dec 29, 2015 at 1:38
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 20 bytes

n->znorder(Mod(2,n))
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ No need for the map command, just use 2.^(1:n)%n. \$\endgroup\$ Commented Dec 29, 2015 at 4:59
2
\$\begingroup\$

Perl 5, 29 bytes

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

Hat tip.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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:

enter image description here

Uses a custom encoding.

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

Improve this answer
\$\endgroup\$
3
  • 3
    \$\begingroup\$ The rainbows and unicorns are strong with this one... \$\endgroup\$ Commented Dec 30, 2015 at 2:21
  • \$\begingroup\$ Somebody come up with UnicornRLE \$\endgroup\$ Commented Dec 31, 2015 at 15:36
  • \$\begingroup\$ Am I the only one getting ((2)2(2))(()) out of the code with @Downgoat's interpreter? \$\endgroup\$ Commented Jan 18, 2016 at 23:13
2
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 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
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

CJam, 15 bytes

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

Peter Taylor saved a byte. Neat!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Rather than 1fe| you could :) and then ) after doing the #. \$\endgroup\$ Commented Dec 30, 2015 at 10:22
  • \$\begingroup\$ 2qi,:)f#_,f%1#) \$\endgroup\$ Commented Dec 30, 2015 at 12:08
  • \$\begingroup\$ Ohh, of course. Thank you. \$\endgroup\$ Commented Dec 30, 2015 at 12:19
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt -æ, 9 bytes

©2pU %N¶1

Try it

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 37 bytes \$\endgroup\$ Commented Mar 15, 2020 at 14:13
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.