Periods of Reciprocals of Integers

[Albert Chan]

(08-06-2018 03:37 AM)Thomas Klemm Wrote:  

(08-06-2018 12:59 AM)Albert Chan Wrote:  A slight optimization is to check if p==n-1 too, and return k+k

Fair point. But we'd still have to run to \(2k\) if we wanted to display the digits.

Hi, Thomas:

If p==n-1 exist, you can deduce the other half digits with 9-complements

To show why it work, i use a simpler fraction, say 1/13:
10^3 (mod 13) = 12, so period = 2*3 = 6

Firsrt 3 repeating digits of 1/13 = floor(1e3/13) = 076
To get the other half repeating digits d:

76000/999999 + d/999999 = 1/13 = 77/1001
76000 + d = 77*999 = (76+1)(1000-1) = 76000 + 1000 - 76 - 1
d = 999 - 76 = 923

-> 1/13 = 0.076 923

A harder example 3/17, 10^8 (mod 17) = 16, so period = 2*8 = 16

First 8 repeating digits of 3/17 = floor(3e8/17) = 17647058

--> 3/17 = 0.17647058 82352941