Periods of Reciprocals of Integers

[Thomas Klemm]

(12-30-2017 02:19 PM)Macumazahn Wrote:  This made me wonder how to determine the period of the decimal representation of the reciprocal of an integer.

In case of \(n=13\) the period \(k=6\) and therefore we can write \(\frac{1}{13}=\frac{76,923}{999,999}\). This is a consequence of the formula to calculate the geometric series.

However this means that \(13\times76,923=999,999\) and thus in general: \(n\) divides \(10^k-1\).
For this to work properly we have to make sure that \(n\) doesn't share divisors with \(10\).

Here's a program for the HP-41:

Code:

LBL "PERIOD"
STO 00 ; n
LBL 00
RCL 00 ; n
2
MOD
X≠0?
GTO 01
LASTX
ST/ 00 ; n
GTO 00
LBL 01
RCL 00 ; n
5
MOD
X≠0?
GTO 02
LASTX
ST/ 00 ; n
GTO 01
LBL 02
CLX
STO 01 ; k
RCL 00 ; n
1
X=Y?
GTO 04
ENTER  ; 1 1
LBL 03 ; 1 p
ST+ 01 ; k'=k+1
X<>Y   ; p 1
10     ; 10 p 1
*      ; 10*p 1
RCL 00 ; n 10*p 1
MOD    ; 10*p%n 1
X<>Y   ; 1 p'
X≠Y?
GTO 03 ; while
LBL 04 ; done
RCL 01 ; k
END

This is a translation of the following Python program:

Code:

def period(n):
    while n % 2 == 0:
        n /= 2
    while n % 5 == 0:
        n /= 5
    k, p = 0, 1
    if n == 1:
        return k
    while True:
        k += 1
        p = p * 10 % n
        if p == 1:
            return k

There are probably more efficient ways to calculate the smallest integer \(k\) such that \(10^k\equiv1(\mod n)\) since it divides the Carmichael Function \(\lambda(n)\). But for this we'd need to know the prime-factors of \(n\).

Kind regards
Thomas