Di kamar saya, saya punya jam culun ini (klik untuk ukuran penuh):

Sebagian besar tidak sulit untuk dipecahkan, tetapi yang untuk 4-jam sangat sulit:

Biasanya, sebagian kecil seperti 1/2 tidak masuk akal dalam aritmatika modular karena hanya bilangan bulat yang terlibat. Maka, cara yang benar adalah dengan melihat ini sebagai kebalikan dari 2, atau dengan kata lain, adalah angka di mana . Dengan kata lain, pemikiran sesaat akan mengungkapkan itu karena .

Namun, hanya dengan menemukan invers multiplikasi akan terlalu mudah sebagai tantangan. Jadi mari kita bahas kesulitan untuk eksponensial, atau dengan kata lain, menemukan logaritma modular atau logaritma diskrit dari 2. Dalam hal ini, 3 adalah logaritma modular 2 berkenaan dengan 7. Bagi Anda dengan teori bilangan / aljabar abstrak latar belakang, ini berarti menghitung urutan multiplikasi dari 2 modulo n.

Tantangan

Diberikan bilangan bulat ganjil positif nlebih besar dari 1, menghasilkan bilangan bulat positif terkecil di xmana .

Contohnya

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 

Jelly , 6 byte

R2*%i1

Cobalah online!

Bagaimana itu bekerja

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 byte

f!t.^2TQ

Test Suite .

filters dari default 1 hingga menemukan beberapa x sedemikian rupa sehingga eksponensial modular dengan 2 dan input sama dengan 1.

Python, 32 byte

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

Dimulai dengan 2, gandakan modulo hingga hasilnya 1, bertambah secara rekursif setiap kali, dan berakhir dengan hitungan 1 untuk nilai awal 2.

Mathematica, 24 byte

2~MultiplicativeOrder~#&

Saya hanya menggunakan built-in untuk ini.

APL, 8 byte

1⍳⍨⊢|2*⍳

Ini adalah kereta fungsi monadik yang menerima integer di sebelah kanan dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel.

Penjelasan (memanggil 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

Perhatikan bahwa hasilnya mungkin salah untuk input besar karena eksponensial dibulatkan.

Pyth, 14 byte

VQIq%^2hNQ1hNB

Penjelasan:

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

Coba di sini

JavaScript (ES6), 28 byte

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

Berdasarkan pendekatan rekursif @ xnor yang brilian.

05AB1E , 11 byte

Kode:

DUG2NmX%iNq

Penjelasan:

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

Julia, 25 24 byte

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

Ini sederhana - 2.^(1:n)%nmenemukan kekuatan 2 dalam set, ∪adalah union, tetapi berfungsi sebagai uniquedan mengembalikan hanya satu dari masing-masing kekuatan unik (dan karena ini adalah operator infix, saya dapat bergabung dengan 1 untuk menghemat satu byte dari ∪(2.^(1:n)%n)pendekatan). Kemudian endofmenghitung jumlah kekuatan unik, karena setelah mencapai 1, itu hanya akan mengulangi kekuatan yang ada, sehingga akan ada nilai unik sebanyak kekuatan yang menghasilkan 1.

Serius, 14 byte

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

Hex Dump:

312c3bbb5260d3bd4025604da175

Cobalah secara Online

Penjelasan:

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

Haskell, 30 byte

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

Argumen helper tdigandakan modulo nsetiap langkah sampai sama dengan 1.

Japt, 17 byte

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

Cobalah online!

Ini akan menjadi tiga byte lebih pendek jika Japt memiliki fungsi "temukan item pertama yang cocok dengan kondisi ini". Mulai kerjakan satu

Bagaimana itu bekerja

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 byte

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

Julia, 33 26 byte

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

Ini adalah fungsi lambda yang menerima integer dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel.

Kami membangun sebuah array sebagai 2 dinaikkan ke setiap daya integer dari 1 ke n, kemudian kami menemukan indeks 1 pertama dalam array ini.

Disimpan 7 byte berkat Glen O!

Perl 5, 29 byte

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

Ujung topi.

MATL , 13 byte

it:Hw^w\1=f1)

Berjalan pada Oktaf dengan komit GitHub saat ini dari kompiler.

Berfungsi untuk input hingga 51(karena keterbatasan doubletipe data).

Contoh

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

Penjelasan

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 ✨✨✨✨✨✨✨ 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐🐐 ) ) ( 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤🌤 🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄🦄 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 ( ) )

Saya mencoba membuat unicorn bahasa golf yang serius tapi itu agak sulit ...

Mudah-mudahan saya akan menemukan cara untuk mempertahankan "unicorn-ness" dari bahasa sementara membuat banyak kurang byte

Gambar:

Menggunakan penyandian khusus .

Jawaban ini tidak bersaing karena menggunakan versi Unicorn yang dibuat setelah bahasa ini

𝔼𝕊𝕄𝕚𝕟, 11 karakter / 22 byte

↻2ⁿḁ%ï>1)⧺ḁ

Try it here (Firefox only).

Menggunakan loop sementara. Ini adalah salah satu dari beberapa kali loop sementara lebih baik daripada memetakan rentang.

Penjelasan

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

CJam, 15 byte

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

Peter Taylor menyimpan satu byte. Rapi!

Prolog, 55 byte

Kode:

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

Dijelaskan:

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

Contoh:

p(195).
12

Cobalah online di sini