25
4
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
1Follow-up challenge: calculate that dot chart value thingy – Conor O'Brien – 2015-12-28T23:53:32.167
3@CᴏɴᴏʀO'Bʀɪᴇɴ: That's just binary. – El'endia Starman – 2015-12-29T00:18:45.910
2Graphical input! – Conor O'Brien – 2015-12-29T00:19:28.583
1https://oeis.org/A002326 – msh210 – 2015-12-29T07:05:42.117
Regarding the clock, most of these make sense to me, but not 1, 4, or 5. Your explanation for 4 just confirms what I suspect: it's really a one-way hash function: if you know the value, you can confirm it with the formula. The explanation (assuming it is the correct one) yields multiple possible values for x. Is it 4 o'clock or 11 o'clock? – Otheus – 2015-12-29T10:05:43.983
2
@Otheus: 1 is apparently supposed to be Legendre's constant, but in a strange notation, and 5 is due to phi. Regarding the multiple possible values for x, 11 is equivalent to 4 modulo 7, so they're really the same.
– El'endia Starman – 2015-12-29T10:26:57.407We all know (1/2)%7=1/2. – SuperJedi224 – 2015-12-29T13:33:55.880
2@SuperJedi224 Who said that that
2^-1 == 1/2
? – Dennis – 2015-12-29T15:58:38.157@Dennis Properties of exponents. Unless that's bitwise XOR, of course. – SuperJedi224 – 2015-12-29T16:09:16.477
6
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. – Dennis – 2015-12-29T16:15:33.5474Modular arithmetic is weird. – SuperJedi224 – 2015-12-29T16:28:10.653
3@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". – Todd Wilcox – 2015-12-29T18:17:32.190
"Regarding the multiple possible values for x, 11 is equivalent to 4 modulo 7, so they're really the same". Ugh, so it's a 5 hour clock. :P – Otheus – 2015-12-30T07:33:35.647