Écrivez une fonction qui prend un seul entier positif n et renvoie la période de la représentation décimale de 1 / n .

Cas de test:

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

C'est du code-golf . Les modules intégrés ou bibliothèques qui renvoient directement la période ne sont pas autorisés. Les nombres jusqu'à au moins 100 000 devraient fonctionner dans un délai raisonnable (au plus plusieurs minutes).

APL, 19 caractères / octets *

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

Nars2000 . La version précédente était erronée sur certains chiffres, cela devrait être correct. Je l'ai vérifié manuellement sur tous les numéros jusqu'à 50.

Encore une fois, le mérite revient à Ben Reich pour l'idée de regarder la période de10^i (mod x)

Vue éclatée

{                     ⍳⍵}   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

Exemples

      {(↑⍳⍨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 peut être écrit dans son propre jeu de caractères à un octet (hérité) qui mappe les symboles APL aux valeurs supérieures de 128 octets. Par conséquent, aux fins de la notation, un programme de N caractères qui utilise uniquement des caractères ASCII et des symboles APL peut être considéré comme long de N octets.}

GolfScript ( 42 27)

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

Temps de référence: 5 secondes. Code de référence:

'"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

Nous remercions Ben Reich pour l'idée centrale de regarder la période de 10^i (mod x).

Explication

La période pest définie comme le plus petit entier positif tel que pour tout suffisamment grand inous avons frac(10^i * 1/x) = frac(10^(i+p) * 1/x). Nous pouvons simplifier cela légèrement frac(10^i / x) = frac(10^(i+p) / x). Maintenant, frac(a / x) = frac(b / x)IFF a == b (mod x), donc nous cherchons le plus petit entier positif tel que pour tout suffisamment grand i: 10^i == 10^(i+p) (mod x).

Supposons 10^i == 10^(i+p) (mod x). Alors 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); donc une fois que nous obtenons une répétition, nous sommes dans un cycle incassable.

Il n'y a que xdes valeurs distinctes (mod x), donc par le principe du pigeonhole nous devons obtenir une répétition dans les premières x + 1valeurs de 10^i (mod x).

Le code ci-dessus consiste donc à calculer les x + 2valeurs de 10^i (mod x)*. Ensuite, le dernier est garanti comme une répétition, et en inversant la liste et en la recherchant, je peux trouver l'occurrence la plus récente. De plus, parce que je ne fais qu'une seule recherche, c'est le temps pseudo-linéaire.

* L'extra est de gérer le cas spécial x = 1, parce que je ne réduis pas 10^0 (mod x)et donc je chercherais un 0po [1].

Golfscript - 26 octets

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

Edit: mis à jour pour sortir 1si la décimale se termine, plutôt que la longueur de la représentation décimale.

Une version assez efficace. La valeur 67890 s'exécute en environ 10 secondes et 99991 environ 20 secondes. C'est un peu plus lent qu'auparavant (environ la moitié de la vitesse), car la plage itérée a été doublée, la première moitié étant ignorée.

Alternative, également 26 octets

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

Celui-ci fonctionne en itérant sur la chaîne "\n"*(2*i+1), où iest la valeur transmise à la fonction. La valeur transmise au bloc à chaque fois est la valeur ordinale de "\n", qui est 10 .

C'est )^^un peu une solution de contournement. Lorsque vous annulez un caractère d'une chaîne, le résultat est la valeur ordinale du caractère supprimé, comme mentionné ci-dessus. Cependant, l'ajout de cette valeur ajoutera la représentation sous forme de chaîne de ce nombre, plutôt que le caractère - un comportement assez asymétrique, et à mon avis, un défaut de conception. Si vous vouliez vraiment le faire, la première chaîne ne coûterait qu'un octet.

Une copie supplémentaire de la valeur finale est déjà sur la pile, donc je supprime à nouveau la valeur finale ), la xor avec la chaîne, puis la xor à nouveau, afin que tous les caractères ajoutés ou supprimés par le premier xor soient restaurés. Si int op stringétaient traités comme un caractère, plutôt que sa représentation sous forme de chaîne, )^^pourraient être remplacés par |.

Notez que tandis que les chaînes (qui dans Golfscript sont stockées sous forme de tableau d'ints) afficheront la valeur de chaque caractère mod 256 , les valeurs de chaque caractère peuvent elles-mêmes être en dehors de cette plage. Lors du test d'unicité (via des opérations définies) ou de confinement (via ?), c'est la valeur réelle qui est comparée, plutôt que la valeur d'affichage.

Un fichier patch pour l' interpréteur Golfscript actuel :

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

Ce qui précède n'affectera que le comportement de string op int(et vice versa), où opest l'un des
+-|&^. Tout le reste n'est pas affecté, y compris le comportement de Gint`.

La solution suivante de 24 octets deviendrait alors valide:

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

Et cela corrige également beaucoup d'autres solutions de contournement vraiment laides .

Python - 48 octets

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

Pas la solution la plus efficace, mais raisonnable pour des valeurs inférieures à 100 000 .

FWIW, l'élément central est identique à ma solution pour Générer des nombres cycliques en décimal .

Une version plus efficace du même code ( 70 octets ):

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

La valeur 99991 prend moins d'une seconde.

GolfScript, 48 47 46

Merci à @PeterTaylor d'avoir coupé deux caractères.

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

J'ai essayé d'utiliser J, mais cela m'a donné toutes sortes de résultats étranges.

Testez en ligne

Cela divise fondamentalement 2 et 5 du nombre (2 et 5 sont les facteurs premiers de 10, et leurs inverses se terminent et remplissent l'algorithme), puis le plus petit entier n tel que le nombre résultant divise 10 ^ n - 1 est la période.

Perl, 52 caractères

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

Il s'agit d'une mise en œuvre simple de l'approche directe. (Heureusement, l'approche directe est également assez efficace: grâce à l'arithmétique modulo, les mathématiques n'ont jamais à traiter un nombre supérieur à 10 fois la valeur d'entrée.)

Comme le défi spécifiait une fonction, je me suis senti obligé de (re) initialiser mes variables, ce que je ne prendrais pas la peine de faire pour un programme complet. De même, ~~dans l'instruction finale est inutile si la fonction peut être certaine qu'elle sera invoquée dans un contexte scalaire.

Clojure, 102, 117, 115, 106

non formaté:

(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)))))

formaté:

(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)))))

Le temps de course varie avec la période. Presque instantané sur mon ordinateur pour les valeurs d'échantillon.

Fondamentalement, cela calcule le résultat de la soustraction après chaque étape de la division longue. Un cycle est détecté si à tout moment ce nombre est le même que celui qui a été calculé avant lui.

(non concurrent) Pyth

fq.^;yTQ.^;TQ

Utilise l' algorithme tortue-et-lièvre ( plus d'informations ).

Regardez-le passer tous les tests.