Period of the decimal representation

Question

Write a function which takes a single positive integer n and returns the period of the decimal representation of 1/n.

Test cases:

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

This is code-golf. Built-ins or libraries which return the period directly are not permitted. Numbers up to at least 100000 should work within reasonable time (at most several minutes).

Answer 1

APL, 19 chars/bytes*

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

Nars2000. The previous version was wrong on some numbers, this should be right. I manually checked it on all numbers up to 50.

Again, credit goes to Ben Reich for the idea of looking at the period of 10^i (mod x)

Exploded view

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

Examples

      {(↑⍳⍨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 can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.}

Answer 2

GolfScript (42 27)

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

Benchmark time: 5 secs. Benchmarking code:

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

Credit to Ben Reich for the core idea of looking at the period of 10^i (mod x).

Explanation

The period p is defined as the smallest positive integer such that for all sufficiently large i we have frac(10^i * 1/x) = frac(10^(i+p) * 1/x). We can simplify that slightly to frac(10^i / x) = frac(10^(i+p) / x). Now, frac(a / x) = frac(b / x) iff a == b (mod x), so we're looking for the smallest positive integer such that for all sufficiently large i: 10^i == 10^(i+p) (mod x).

Suppose 10^i == 10^(i+p) (mod x). Then 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); so once we get a repetition, we're in an unbreakable cycle.

There are only x distinct values (mod x), so by the pigeonhole principle we must get a repetition in the first x + 1 values of 10^i (mod x).

So what the code above does is to compute x + 2 values of 10^i (mod x)*. Then the last one is guaranteed to be a repetition, and by reversing the list and searching for it I can find the most recent occurrence. Moreover, because I'm only doing the one search this is pseudolinear time.

* The extra one is to handle the special case x = 1, because I don't reduce 10^0 (mod x) and so I'd be looking for a 0 in [1].

Answer 3

Golfscript - 26 bytes

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

Edit: updated to output 1 if the decimal terminates, rather than the length of the decimal representation.

A fairly efficient version. The value 67890 runs in approximately 10 seconds, and 99991 around 20 seconds. It's a bit slower than it was before (roughly half as fast), because the range that is iterated has been doubled, the first half of which is ignored.

Alternative, also 26 bytes

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

This one works by iterating over the string "\n"*(2*i+1), where i is the value passed to the function. The value passed to the block each time is the ordinal value of "\n", which is 10.

The )^^ is a bit of a work-around. When you uncons a character from a string, the result is the ordinal value of the character removed, as mentioned above. However, appending that value back on will append the string representation of that number, rather than the character - fairly nonsymmetric behavior, and in my opinion a design flaw. If you actually wanted to do that, stringifying first would only cost one byte.

An extra copy of the final value is already on the stack, so I remove the final value again ), xor it with the string, and then xor it again, so that any characters which were added or removed by the first xor are restored. If int op string were treated as a character, rather than its string representation, )^^ could be replaced by |.

Note that while strings (which in Golfscript are stored as an array of ints) will display the value of each character mod 256, the values of each character may themselves be outside this range. When testing for uniqueness (via set operations) or containedness (via ?), it is the actual value that is compared, rather than the display value.

A patch file for the current Golfscript interpreter:

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

The above will only affect the behavior of string op int (and vice versa), where op is one of
+-|&^. Everything else remains unaffected, including the behavior of Gint`.

The following 24 byte solution would then become valid:

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

And this also fixes a lot of other really ugly work-arounds.

---

Python - 48 bytes

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

Not the most efficient solution, but reasonable for values less than 100000.

FWIW, the core element is identical to my solution for Generate cyclic numbers in decimal.

A more efficient version of the same code (70 bytes):

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

The value 99991 takes less than a second.

Answer 4

GolfScript, 48 47 46

Thanks to @PeterTaylor for chopping two chars off.

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

I tried using J, but it kept giving me all sorts of strange results.

Test online

This basically divides 2 and 5 out of the number (2 and 5 are the prime factors of 10, and their reciprocals terminate, and stuff up the algorithm), then the lowest integer n such that the resulting number divides 10^n - 1 is the period.

Answer 5

Perl, 52 characters

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

This is an uncomplicated implementation of the direct approach. (Fortunately the direct approach is also pretty efficient: thanks to modulo arithmetic, the math never has to deal with a number more than 10 times the input value.)

Since the challenge specified a function, I felt compelled to (re-)initialize my variables, something I wouldn't bother doing for a complete program. Likewise, the ~~ in the final statement is unnecessary if the function can be certain it will be invoked in a scalar context.

Answer 6

Clojure, 102, 117, 115, 106

unformated:

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

formatted:

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

Running time scales with the period. Almost instantaneous on my computer for the sample values.

Basically, this calculates the result of the subtraction after each step in long division. A cycle is detected if at any point that number is the same as one that has been calculated before it.

Answer 7

(non-competing) Pyth

fq.^;yTQ.^;TQ

Uses turtle-and-hare algorithm (more information).

Watch it pass every test.