20
\$\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\$
7
  • \$\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
    Commented Jan 15, 2014 at 11:07
  • 1
    \$\begingroup\$ @FireFly Algorithms must provide the correct answer. \$\endgroup\$
    – Howard
    Commented Jan 15, 2014 at 11:34
  • 3
    \$\begingroup\$ Why would 1 return 1? I would think 0? \$\endgroup\$
    – Timtech
    Commented Jan 30, 2014 at 12:20
  • 3
    \$\begingroup\$ @Timtech 1.00000000000000000000000000000000000 \$\endgroup\$
    – Cruncher
    Commented Jan 30, 2014 at 21:04
  • 1
    \$\begingroup\$ A051626, but all 0s are replaced with 1s \$\endgroup\$
    – bigyihsuan
    Commented Mar 17, 2022 at 17:06

11 Answers 11

12
+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.

\$\endgroup\$
9
  • \$\begingroup\$ I can't get the correct answer for e.g. input 20. Can you please verify? \$\endgroup\$
    – Howard
    Commented Feb 2, 2014 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
    Commented Feb 2, 2014 at 18:24
  • \$\begingroup\$ The correct answer would be 1, since 1/20 = 0.05_0_. \$\endgroup\$
    – Howard
    Commented Feb 3, 2014 at 6:05
  • \$\begingroup\$ I see. Give me a bit, I'll revise my answer. \$\endgroup\$
    – Tobia
    Commented Feb 3, 2014 at 7:42
  • \$\begingroup\$ 4 seems that it would give the wrong answer too, because 10 != 100 (mod 4). \$\endgroup\$ Commented Feb 3, 2014 at 11:08
8
\$\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].

\$\endgroup\$
1
  • \$\begingroup\$ Awesome! I've deleted my answer since a better solution! – \$\endgroup\$
    – Ben Reich
    Commented Jan 15, 2014 at 20:59
8
\$\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.

\$\endgroup\$
12
  • \$\begingroup\$ @PeterTaylor it ors the array onto an empty string. Because it's a set-wise operation, all duplicates are removed beforehand. \$\endgroup\$
    – primo
    Commented Jan 30, 2014 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\$ Commented Jan 30, 2014 at 23:30
  • 1
    \$\begingroup\$ @PeterTaylor fixed. \$\endgroup\$
    – primo
    Commented Jan 31, 2014 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\$ Commented Jan 31, 2014 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
    Commented Jan 31, 2014 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.

\$\endgroup\$
4
  • 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\$ Commented Jan 15, 2014 at 12:59
  • \$\begingroup\$ @PeterTaylor thanks, hadn't thought of that \$\endgroup\$
    – Volatility
    Commented Jan 15, 2014 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\$ Commented Jan 15, 2014 at 17:03
  • 2
    \$\begingroup\$ Another micro-optimisation: int array ,)\; can be shortened to int array +,. \$\endgroup\$ Commented Jan 15, 2014 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.

\$\endgroup\$
1
  • \$\begingroup\$ Try on input 20 where it yields the wrong result. \$\endgroup\$
    – Howard
    Commented Feb 2, 2014 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.

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

05AB1E, 9 bytes

ÌLR°I%ćk>

Port of @PeterTaylor GolfScript answer, so make sure to upvote him as well!

Try it online or verify almost all test cases. The last test case is omitted, which takes little over a minute.

If we want to output all test cases in less than a second, a port of @primo's Python answer could be used, which comes in at 14 bytes with a minor alternative of the same approach using a cumulative right-reduce:

>LTªÅ«T*I%}ćk>

Try it online or verify all test cases.

Explanation:

Based on the input \$n\$, I first generate a list within the range \$[n+1,1]\$. And then find the first 1-based index of a value \$x\$ which is truthy for \$10^x\pmod n=10^{n+2}\pmod n\$.

Ì          # Increase the (implicit) input-integer by 2
 L         # Pop and push a list in the range [1,input+2]
  R        # Reverse it to the range [input+2,1]
   °       # Map each value to 10 to the power that value
    I%     # Modulo the input
      ć    # Extract head; pop and push remainder-list and first item separately
       k   # Get the 0-based index of this 10**(input+2) in the list of
           # [10**(input+1),10**input,...,100,10]
        >  # Increase this by 1 to make it a 1-based index
           # (which is output implicitly as result)
>L         # Push a list in the range [1,input+1]
  Tª       # Append a trailing 10
    Å«     # Cumulative right-reduce, keeping all intermediate results:
      T*   #  Multiply the current integer by 10
        I% #  Modulo the input
     }     # After the right-reduce:
      ćk>  # Get the 1-based index of the extracted head, similar as above
           # (which is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Pyth, 13 bytes

fq.^;yTQ.^;TQ

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

Watch it pass every test.

\$\endgroup\$
1
\$\begingroup\$

Vyxal r, 8 bytes

⇧ɾṘ↵%ḣḟ›

Try it Online!

Port of 05AB1E.

How?

⇧ɾṘ↵%ḣḟ›
⇧ɾ        # Push range [1, (implicit) input + 2]
  Ṙ       # Reverse to make it range [input + 2, 1]
   ↵      # Map each value to 10 to the power of it
    %     # Modulo by the (implicit) input
     ḣ    # Head extract, push a[0] and a[1:]
      ḟ   # Get the index of this a[0] in this a[1:]
       ›  # Increment to make this a one-based index
\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 33 bytes

n->znorder(Mod(10,n/gcd(n,10^n)))

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 7 bytes

üpßN▲╞§

Run and debug it

Approach:

  1. Multiply by 10
  2. Keep only fractional part
  3. Repeat until a loop of values is found
  4. Keep only the loop
  5. Get the length
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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