Escriba una función que tome un solo entero positivo n y devuelva el período de la representación decimal de 1 / n .

Casos de prueba:

1 -> 1               # 1/1 = 1.0000...... = 1._0
2 -> 1               # 1/2 = 0.5000...... = 0.5_0
3 -> 1               # 1/3 = 0.3333...... = 0._3
7 -> 6               # 1/7 = 0.14285714.. = 0._142857
13 -> 6
14 -> 6
123 -> 5
345 -> 22
654 -> 108
12345 -> 822
67890 -> 120

Este es el código de golf . No se permiten las incorporaciones o bibliotecas que devuelven el período directamente. Los números de hasta al menos 100000 deberían funcionar dentro de un tiempo razonable (como máximo varios minutos).

APL, 19 caracteres / bytes *

{(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}

Nars2000 . La versión anterior era incorrecta en algunos números, esto debería ser correcto. Lo revisé manualmente en todos los números hasta el 50.

Nuevamente, el crédito va a Ben Reich por la idea de mirar el período de10^i (mod x)

Vista en despiece ordenado

{                     ⍳⍵}   generate all naturals up to the argument ⍵
                 10x*       raise 10 to each of them, with unlimited precision
              ⍵|            compute the respective remainders mod ⍵
            ⌽               reverse the list
 (  ⍳⍨    )                 (fork) find the position of the first occurrence
  ↑                         of the fist element of the list
       1∘↓                  in the remainder of the list

Ejemplos

      {(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}¨1 2 3 7 13 14 123 345 654 12345 67890
1 1 1 6 6 6 5 22 108 822 120

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ^{*: APL se puede escribir en su propio} juego de
^{caracteres de un solo byte (heredado) que asigna símbolos APL a los valores superiores de 128 bytes. Por lo tanto, para fines de puntuación, un programa de N caracteres que solo usa caracteres ASCII y símbolos APL puede considerarse que tiene una longitud de N bytes.}

GolfScript ( 42 27)

{:x)1\[{.10*x%}*]-1%(?)}:P;

Tiempo de referencia: 5 segundos. Código de evaluación comparativa:

'"The time is #{Time.now#1
}"'~ puts
[1 2 3 7 13 14 123 345 654 12345 67890 99991]{[P]p}%
'"The time is #{Time.now#2
}"'~ puts

Gracias a Ben Reich por la idea central de mirar el período de 10^i (mod x).

Explicación

El período pse define como el entero positivo más pequeño de tal manera que para todos lo suficientemente grande ique tenemos frac(10^i * 1/x) = frac(10^(i+p) * 1/x). Podemos simplificar eso ligeramente a frac(10^i / x) = frac(10^(i+p) / x). Ahora, frac(a / x) = frac(b / x)si y sólo si a == b (mod x), por lo que estamos buscando el menor entero positivo tal que para todo suficientemente grande i: 10^i == 10^(i+p) (mod x).

Supongamos 10^i == 10^(i+p) (mod x). Entonces 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); así que una vez que tenemos una repetición, estamos en un ciclo inquebrantable.

Solo hay xvalores distintos (mod x), por lo que, según el principio del casillero, debemos repetir los primeros x + 1valores de 10^i (mod x).

Entonces, lo que hace el código anterior es calcular los x + 2valores de 10^i (mod x)*. Entonces se garantiza que la última será una repetición, y al invertir la lista y buscarla puedo encontrar la ocurrencia más reciente. Además, debido a que solo estoy haciendo una búsqueda, este es el tiempo seudolinear.

* El único extra es para manejar el caso especial x = 1, porque no reducen 10^0 (mod x)y por lo que estaría buscando una 0en [1].

Golfscript - 26 bytes

{:i.)+.,{;10*i%.}%i>|,}:f;

Editar: actualizado a la salida 1si el decimal termina, en lugar de la longitud de la representación decimal.

Una versión bastante eficiente. El valor 67890 se ejecuta en aproximadamente 10 segundos y 99991 alrededor de 20 segundos. Es un poco más lento de lo que era antes (aproximadamente la mitad de rápido), porque el rango iterado se ha duplicado, la primera mitad del cual se ignora.

Alternativa, también 26 bytes

{:i.)+.n*{*i%.}%i>)^^,}:f;

Este funciona iterando sobre la cadena "\n"*(2*i+1), donde ies el valor pasado a la función. El valor pasado al bloque cada vez es el valor ordinal de "\n", que es 10 .

El )^^es un poco una solución alternativa. Cuando desconecta un carácter de una cadena, el resultado es el valor ordinal del carácter eliminado, como se mencionó anteriormente. Sin embargo, agregar ese valor nuevamente agregará la representación de cadena de ese número, en lugar del carácter, un comportamiento bastante no simétrico y, en mi opinión, un defecto de diseño. Si realmente quisieras hacer eso, encadenar primero solo costaría un byte.

Ya hay una copia adicional del valor final en la pila, por lo que elimino el valor final nuevamente ), lo xo con la cadena y luego lo vuelvo a hacer, de modo que se restauran los caracteres que se agregaron o eliminaron. Si int op stringse tratara como un carácter, en lugar de su representación de cadena, )^^podría reemplazarse por |.

Tenga en cuenta que mientras las cadenas (que en Golfscript se almacenan como una matriz de entradas) mostrarán el valor de cada mod de carácter 256 , los valores de cada carácter pueden estar fuera de este rango. Cuando se prueba la unicidad (mediante operaciones de configuración) o la contención (mediante ?), se compara el valor real, en lugar del valor de visualización.

Un archivo de parche para intérprete actual de Golfscript :

61c61
<       to_gs
---
>       Gstring.new([self])

Lo anterior solo afectará el comportamiento de string op int(y viceversa), dondeop es uno de
+-|&^. Todo lo demás no se ve afectado, incluido el comportamiento de Gint`.

Los siguientes 24 bytes solución de pasaría a ser válida:

{:i.)+.n*{*i%.}%i>|,}:f;

Y esto también soluciona muchos otros realmente feas .

Python - 48 bytes

f=lambda n:len(set(10**-~i%n for i in range(n)))

No es la solución más eficiente, pero razonable para valores inferiores a 100000 .

FWIW, el elemento central es idéntico a mi solución para Generar números cíclicos en decimal .

Una versión más eficiente del mismo código ( 70 bytes ):

 def f(n):
  a=[];i=10%n
  while i not in a:a+=i,;i=i*10%n
  return len(a)

El valor 99991 toma menos de un segundo.

GolfScript, 48 47 46

Gracias a @PeterTaylor por cortar dos caracteres.

{2{1$1$%!{.@\/\d}*}:d~;5d;9{2$%}{10*9+}/+,}:f;

Intenté usar J, pero me dio todo tipo de resultados extraños.

Prueba en línea

Básicamente, esto divide 2 y 5 del número (2 y 5 son los factores primos de 10, y sus recíprocos terminan y rellenan el algoritmo), luego el número entero más bajo n tal que el número resultante divide 10 ^ n - 1 es el período.

Perl, 52 caracteres

sub f{($p,%r)=1;1until$r{$p=$p*10%$_[0]}++;~~keys%r}

Esta es una implementación sin complicaciones del enfoque directo. (Afortunadamente, el enfoque directo también es bastante eficiente: gracias a la aritmética de módulo, las matemáticas nunca tienen que lidiar con un número más de 10 veces el valor de entrada).

Como el desafío especificaba una función, me sentí obligado a (re) inicializar mis variables, algo que no me molestaría en hacer para un programa completo. Del mismo modo, la ~~declaración final no es necesaria si la función puede estar segura de que se invocará en un contexto escalar.

Clojure, 102, 117, 115106

sin formato:

(defn r([n](r{}(iterate #(mod(* % 10)n)10)0))([a[f & s]i](if(a f)(- i(a f))(recur(assoc a f i)s(inc i)))))

formateado:

(defn r
  ([n] (r {} (iterate #(mod (* % 10) n) 10) 0))
  ([a [f & s] i]
    (if (a f)
      (- i (a f))
      (recur
        (assoc a f i)
        s
        (inc i)))))

El tiempo de ejecución se escala con el período. Casi instantáneo en mi computadora para los valores de muestra.

Básicamente, esto calcula el resultado de la resta después de cada paso en la división larga. Se detecta un ciclo si en algún punto ese número es el mismo que el que se calculó antes.

(no competidor) Pyth

fq.^;yTQ.^;TQ

Utiliza el algoritmo de tortuga y liebre ( más información ).

Míralo pasar cada prueba.