Dans ma chambre, j'ai cette horloge geek (cliquez pour agrandir):

La plupart d'entre eux ne sont pas difficiles à comprendre, mais celui pour 4 heures est particulièrement délicat:

Normalement, une fraction comme 1/2 n'a pas de sens en arithmétique modulaire car seuls les entiers sont impliqués. La bonne façon, alors, est de voir cela comme l' inverse de 2, ou pour le dire autrement, c'est le nombre où . En d'autres termes, une pensée d'un moment révélera cela parce que .

Cependant, trouver simplement l' inverse multiplicatif serait beaucoup trop facile comme défi. Donc, augmentons la difficulté de l'exponentiation, ou en d'autres termes, trouver le logarithme modulaire ou logarithme discret de 2. Dans ce cas, 3 est le logarithme modulaire de 2 par rapport à 7. Pour ceux d'entre vous qui ont la théorie des nombres / l'algèbre abstraite fond, cela signifie calculer l'ordre multiplicatif de 2 modulo n.

Le défi

Étant donné un entier impair positif nsupérieur à 1, affichez le plus petit entier positif xoù .

Exemples

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 

Gelée , 6 octets

R2*%i1

Essayez-le en ligne!

Comment ça marche

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 octets

f!t.^2TQ

Suite de tests .

filtre par défaut de 1 jusqu'à ce qu'il trouve un certain x tel que l'exponentiation modulaire avec 2 et l'entrée est égale à 1.

Python, 32 octets

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

Commençant par 2, double modulo n jusqu'à ce que le résultat soit 1, incrémentant récursivement à chaque fois, et se terminant par un compte de 1 pour la valeur initiale de 2.

Mathematica, 24 octets

2~MultiplicativeOrder~#&

Je viens d'utiliser un intégré pour cela.

APL, 8 octets

1⍳⍨⊢|2*⍳

Il s'agit d'un train de fonctions monadique qui accepte un entier à droite et renvoie un entier. Pour l'appeler, affectez-le à une variable.

Explication (appel de l'entrée 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

Notez que le résultat peut être incorrect pour les grandes entrées car l'exponentielle est arrondie.

Pyth, 14 octets

VQIq%^2hNQ1hNB

Explication:

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

Essayez-le ici

JavaScript (ES6), 28 octets

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

Basé sur la brillante approche récursive de @ xnor.

05AB1E , 11 octets

Code:

DUG2NmX%iNq

Explication:

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 octets

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

C'est simple - 2.^(1:n)%ntrouve les puissances de 2 dans l'ensemble, ∪est union, mais ne sert uniqueet ne renvoie qu'une seule de chaque puissance unique (et parce que c'est un opérateur d'infixe, je peux l'union avec 1 pour économiser un octet sur l' ∪(2.^(1:n)%n)approche). ensuiteendofCompte le nombre de pouvoirs uniques, car une fois qu'il atteint 1, il ne fera que répéter les pouvoirs existants, il y aura donc autant de valeurs uniques que la puissance qui produit 1.

Sérieusement, 14 octets

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

Vidage hexadécimal:

312c3bbb5260d3bd4025604da175

Essayez-le en ligne

Explication:

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

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

L'argument d'aide test doublé modulo à nchaque étape jusqu'à ce qu'il soit égal à 1.

Japt, 17 octets

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

Essayez-le en ligne!

Ce serait trois octets plus court si Japt avait une fonction "trouver le premier élément qui correspond à cette condition". Commence à travailler sur un

Comment ça marche

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 octets

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

Julia, 33 26 octets

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

Il s'agit d'une fonction lambda qui accepte un entier et renvoie un entier. Pour l'appeler, affectez-le à une variable.

Nous construisons un tableau comme 2 élevé à chaque puissance entière de 1 à n , puis nous trouvons l'indice du premier 1 dans ce tableau.

7 octets enregistrés grâce à Glen O!

Perl 5, 29 octets

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

Pointe de chapeau.

MATL , 13 octets

it:Hw^w\1=f1)

Fonctionne sur Octave avec la validation GitHub actuelle du compilateur.

Fonctionne pour la saisie jusqu'à 51(en raison des limitations du doubletype de données).

Exemple

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

Explication

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

Licorne , 1307 1062 976 octets

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

J'essaie de faire de la licorne un langage de golf sérieux mais c'est un peu difficile ...

J'espère que je trouverai un moyen de conserver la "licorne" de la langue tout en faisant beaucoup moins d'octets

Image:

Utilise une coutume encodage .

Cette réponse n'est pas concurrente car elle utilise une version de Unicorn faite après cette langue

𝔼𝕊𝕄𝕚𝕟, 11 caractères / 22 octets

↻2ⁿḁ%ï>1)⧺ḁ

Try it here (Firefox only).

Utilise une boucle while. C'est l'une des rares fois qu'une boucle while est meilleure que le mappage sur une plage.

Explication

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

CJam, 15 octets

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

Peter Taylor a enregistré un octet. Soigné!

Prolog, 55 octets

Code:

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

Expliqué:

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

Exemple:

p(195).
12

Essayez-le en ligne ici