16
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The question states that "numbers up to at least 100000 should work within reasonable time", but does the program have to give the right answer for numbers larger than this? Or would it be acceptable to use an algorithm that is only accurate up to 100000? \$\endgroup\$ – FireFly Jan 15 '14 at 11:07
  • 1
    \$\begingroup\$ @FireFly Algorithms must provide the correct answer. \$\endgroup\$ – Howard Jan 15 '14 at 11:34
  • 2
    \$\begingroup\$ Why would 1 return 1? I would think 0? \$\endgroup\$ – Timtech Jan 30 '14 at 12:20
  • \$\begingroup\$ @Timtech 1.00000000000000000000000000000000000 \$\endgroup\$ – Cruncher Jan 30 '14 at 21:04
  • \$\begingroup\$ @Cruncher Oh thanks, I get it now. \$\endgroup\$ – Timtech Jan 30 '14 at 21:19
11
+100
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I can't get the correct answer for e.g. input 20. Can you please verify? \$\endgroup\$ – Howard Feb 2 '14 at 17:27
  • \$\begingroup\$ I followed the examples you posted. In your example, 1/2 = 0.5 -> 1, so naturally 1/20 = 0.05 -> 2. What are you getting? \$\endgroup\$ – Tobia Feb 2 '14 at 18:24
  • \$\begingroup\$ The correct answer would be 1, since 1/20 = 0.05_0_. \$\endgroup\$ – Howard Feb 3 '14 at 6:05
  • \$\begingroup\$ I see. Give me a bit, I'll revise my answer. \$\endgroup\$ – Tobia Feb 3 '14 at 7:42
  • \$\begingroup\$ 4 seems that it would give the wrong answer too, because 10 != 100 (mod 4). \$\endgroup\$ – Peter Taylor Feb 3 '14 at 11:08
7
\$\begingroup\$

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].

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Awesome! I've deleted my answer since a better solution! – \$\endgroup\$ – Ben Reich Jan 15 '14 at 20:59
7
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ @PeterTaylor it ors the array onto an empty string. Because it's a set-wise operation, all duplicates are removed beforehand. \$\endgroup\$ – primo Jan 30 '14 at 23:24
  • \$\begingroup\$ But where does the empty string come from? If the function is to be self-contained I think you're going to have to spend an extra byte and make it .|. \$\endgroup\$ – Peter Taylor Jan 30 '14 at 23:30
  • 1
    \$\begingroup\$ @PeterTaylor fixed. \$\endgroup\$ – primo Jan 31 '14 at 10:03
  • 1
    \$\begingroup\$ Changing the behaviour of string int + would break a lot of programs. I'm not sure how often the other ops are used on that type pair. \$\endgroup\$ – Peter Taylor Jan 31 '14 at 17:55
  • \$\begingroup\$ @PeterTaylor I agree, it would. But consider: convert int to char: []+''+ vs ''+. Append int, as char, to string: []++ vs +. Apend int, as string representation, to string: + vs `+. In it's current implementation, int''+ is synonymous to int`, which seems wasteful considering the verbosity of having to coerce to array, and then coerce to a string if you want the ascii char. \$\endgroup\$ – primo Jan 31 '14 at 18:02
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ If you know which will be the first call to your function then you can inline the definition there. I.e. instead of {...}:d;...d you save 1 char with ...{...}:d~ \$\endgroup\$ – Peter Taylor Jan 15 '14 at 12:59
  • \$\begingroup\$ @PeterTaylor thanks, hadn't thought of that \$\endgroup\$ – Volatility Jan 15 '14 at 13:25
  • 1
    \$\begingroup\$ Having commented to Ben about not leaving f on the stack, I notice that you're doing it too. You should really add a ; to pop the function for fair comparison with other languages. \$\endgroup\$ – Peter Taylor Jan 15 '14 at 17:03
  • 2
    \$\begingroup\$ Another micro-optimisation: int array ,)\; can be shortened to int array +,. \$\endgroup\$ – Peter Taylor Jan 15 '14 at 19:30
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Try on input 20 where it yields the wrong result. \$\endgroup\$ – Howard Feb 2 '14 at 17:30
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The code breaks with input 20. Can you please verify? \$\endgroup\$ – Howard Feb 2 '14 at 17:23
  • \$\begingroup\$ You are right, the above solution is faulty. Gonna see if I can fix it. \$\endgroup\$ – RedDeckWins Feb 2 '14 at 22:27
  • \$\begingroup\$ What is the expected output for 20? \$\endgroup\$ – RedDeckWins Feb 2 '14 at 22:35
  • \$\begingroup\$ The correct answer would be 1. \$\endgroup\$ – Howard Feb 3 '14 at 6:01
  • \$\begingroup\$ Should be good to go, first algorithm would fail on lots of inputs, for example 12 and 20. \$\endgroup\$ – RedDeckWins Feb 3 '14 at 19:36
1
\$\begingroup\$

(non-competing) Pyth

fq.^;yTQ.^;TQ

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

Watch it pass every test.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.