Periods of Reciprocals of Integers

[Thomas Klemm]

Meanwhile I've extracted the redundant code into a "function" reduce:

Code:

LBL "PERIOD"
STO 00      ; n
2           ; 2
XEQ 00      ; reduce(2)
5           ; 5
XEQ 00      ; reduce(5)
CLX         ; 0
STO 01      ; k=0
RCL 00      ; n
1           ; 1 n
X=Y?        ; 1=n?
GTO 02      ; done
ENTER       ; 1 p=1
LBL 01      ; 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?        ; 1=p?
GTO 01      ; while
LBL 02      ; done
RCL 01      ; k
RTN         ; return k
LBL 00      ; reduce(m)
RCL 00      ; n m
X<>Y        ; m n
MOD         ; n%m
X≠0?        ; m ∤ n
RTN         ; done
LASTX       ; m
ST/ 00      ; n'=n/m
GTO 00      ; reduce
END

If you want to also display the digits you can include the following lines:

Code:

RCL X       ; 10*p 10*p 1
RCL 00      ; n 10*p 10*p 1
/           ; 10*p/n 10*p 1 1
INT         ; ⌊10*p/n⌋ 10*p 1 1
VIEW X      ; digit
RDN         ; 10*p 1 …

However the result isn't correct for values divisible by 2 or 5.

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

(12-30-2017 02:19 PM)Macumazahn Wrote:  The challenge here is that the program must keep track of all the remainders it has seen, so that it can detect the first repetition.

You could also use Floyd's cycle detection algorithm or a variant thereof. They use only a constant number of memory cells.

Cheers
Thomas