En mi habitación, tengo este reloj geek (haga clic para ampliar):

La mayoría de estos no son difíciles de entender, pero el de las 4 en punto es particularmente complicado:

Normalmente, una fracción como 1/2 no tiene sentido en aritmética modular ya que solo están involucrados los enteros. La forma correcta, entonces, es ver esto como el inverso de 2, o para decirlo de otra manera, es ese número donde . Dicho de esta manera, un momento de pensamiento lo revelará porque sí .

Sin embargo, simplemente encontrar el inverso multiplicativo sería demasiado fácil como un desafío. Entonces, aumentemos la dificultad de la exponenciación, o en otras palabras, encontremos el logaritmo modular o el logaritmo discreto de 2. En este caso, 3 es el logaritmo modular de 2 con respecto a 7. Para aquellos de ustedes con teoría de números / álgebra abstracta antecedentes, esto significa calcular el orden multiplicativo de 2 módulo n.

El reto

Dado un entero impar positivo nmayor que 1, genera el entero positivo más pequeño xdonde .

Ejemplos

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 

Jalea , 6 bytes

R2*%i1

Pruébalo en línea!

Cómo funciona

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

Test Suite .

fse ilumina desde el valor predeterminado de 1 hasta que encuentra alguna x tal que la exponenciación modular con 2 y la entrada sea igual a 1.

Python, 32 bytes

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

Comenzando con 2, dobla el módulo n hasta que el resultado sea 1, incrementándose recursivamente cada vez, y terminando con una cuenta de 1 para el valor inicial de 2.

Mathematica, 24 bytes

2~MultiplicativeOrder~#&

Acabo de usar un incorporado para esto.

APL, 8 bytes

1⍳⍨⊢|2*⍳

Este es un tren de funciones monádicas que acepta un número entero a la derecha y devuelve un número entero. Para llamarlo, asígnelo a una variable.

Explicación (llamando a la entrada 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

Tenga en cuenta que el resultado puede ser incorrecto para entradas grandes ya que el exponencial se redondea.

Pyth, 14 bytes

VQIq%^2hNQ1hNB

Explicación:

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

Pruébalo aquí

JavaScript (ES6), 28 bytes

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

Basado en el brillante enfoque recursivo de @ xnor.

05AB1E , 11 bytes

Código:

DUG2NmX%iNq

Explicación:

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 bytes

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

Esto es simple: 2.^(1:n)%nencuentra los poderes de 2 dentro del conjunto, ∪es union, pero sirve como uniquey devuelve solo uno de cada poder único (y debido a que es un operador infijo, puedo unirme con 1 para guardar un byte sobre el ∪(2.^(1:n)%n)enfoque). Luego endofcuenta el número de poderes únicos, porque una vez que llegue a 1, solo repetirá los poderes existentes, por lo que habrá tantos valores únicos como el poder que produce 1.

En serio, 14 bytes

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

Hex Dump:

312c3bbb5260d3bd4025604da175

Pruébalo en línea

Explicación:

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

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

El argumento auxiliar tse duplica módulo a ncada paso hasta que sea igual a 1.

Japt, 17 bytes

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

Pruébalo en línea!

Esto sería tres bytes más corto si Japt tuviera la función "buscar el primer elemento que coincida con esta condición". Comienza a trabajar en uno

Cómo funciona

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)

Esta es una función lambda que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.

Construimos un conjunto como 2 elevado a cada potencia entera de 1 a n, luego encontramos el índice del primer 1 en este conjunto.

Guardado 7 bytes gracias a Glen O!

Perl 5, 29 bytes

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

Punta de sombrero.

MATL , 13 bytes

it:Hw^w\1=f1)

Se ejecuta en Octave con la confirmación GitHub actual del compilador.

Funciona para entrada hasta 51(debido a limitaciones del doubletipo de datos).

Ejemplo

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

Explicación

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

Unicornio , 1307 1062 976 bytes

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

Estoy tratando de hacer del unicornio un lenguaje de golf serio, pero eso es un poco difícil ...

Espero encontrar una manera de retener el "unicornio" del lenguaje mientras hago muchos menos bytes

Imagen:

Utiliza una codificación personalizada .

Esta respuesta no es competitiva porque usa una versión de Unicorn hecha después de este idioma

𝔼𝕊𝕄𝕚𝕟, 11 caracteres / 22 bytes

↻2ⁿḁ%ï>1)⧺ḁ

Try it here (Firefox only).

Utiliza un bucle while. Esta es una de las pocas veces que un bucle while es mejor que el mapeo en un rango.

Explicación

          // 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 salvó un byte. ¡Ordenado!

Prólogo, 55 bytes

Código:

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

Explicado:

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

Ejemplo:

p(195).
12

Pruébalo en línea aquí