Periods of Reciprocals of Integers

12302017, 02:19 PM
Post: #1




Periods of Reciprocals of Integers
I'm tutoring a friend's son in math, and recently we've been practicing the longdivision algorithm.
We started looking at the reciprocals of integers, which led to a discussion of their decimal representations. Some of course "terminate" like 1/2 or 1/5. Others repeat forever, like 1/3 or 1/6. For simplicity we considered the "terminating" decimal representations to be repeating decimals, with '0' repeating forever. This made me wonder how to determine the period of the decimal representation of the reciprocal of an integer. I'm sure this has been answered long ago for the general case, but I like to see for myself. To this end I defined the "preamble" to be that part of the decimal that precedes the repeating part, and the "period" to be the length of one cycle of the repeating part. The division algorithm shows both that every such reciprocal 1/n must eventually repeat, and that the maximum possible period is (n1). More to the point, the algorithm also reveals that the repetition of digits begins when a repeated remainder is first encountered. So... I coded up a program, first for my workhorse 32Sii, then for my 41CX. 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. That means a bitmap, which means that the range is limited by available memory. That in turn means making the program as small as possible, while using as few registers as possible. I was able to split the program into six routines, each stored in extended memory. These six routines load one another as required, using GETP. I was able to squeeze the routines down to the point where the largest of the six requires 64 bytes. I just can't get it to 63 (which would improve range). The silver lining in that cloud is that it means I can use a more capable version of one of the other programs ("Q"), as long as that version is no larger than 70 bytes. Unlike the 32Sii which supports 36 bits per register, the 41CX supports only 30. By squeezing the programs down to 70 bytes or less, I can execute SIZE 309 which (since I use two registers for other things) gives the program a maximum range of 30*(3092)=9210. The program actually runs through the division twice  first, to find the matching remainder, and second, to count off the preamble and period. I know it's slow, but I sacrificed time for space in order to maximize range. The user interface is as follows: If flag 00 is set, the program will display the decimal digits as it counts the preamble and period. Flag 01 is set by the program when it completes the count of the preamble and begins counting the period, and cleared when the entire calculation is complete. If flag 02 is set, the program will pause with TIME displayed, to allow a crude measure of elapsed time. Continue the program with R/S to see the actual results. Place "P" in Alpha XEQ GETP Once the initial program "P" is loaded, functionality is as follows: XEQ 01 = reset (reloads program "P") Place positive integer argument n (1 <= n <= 9210) in stackX XEQ 02 = calculate preamble and period Returns: periodlength in stackX preamblelength in stackY n in stackZ (also in LastX) matchedremainder in stackT If somehow we already know the matchedremainder, we can escape the 9210 limit as follows: Place matchedremainder in stackY Place n in stackX XEQ 03 = calculate preamble and period Returns: the same stack of results as XEQ 02 above. The program may be interrupted (and continued) as desired to change flag 00 or 02 settings. However, the display of digits (SF 00) cannot be activated for the first time once the counting of the preamble has begun. The program may be terminated at any time, and reset by XEQ 01. If anyone could tell me how to squeeze program "R" down to 63 bytes without using an additional register or sacrificing functionality, I could extend the range to 9240... Code: 1 LBL "P" Code: 1 LBL "R" Code: 1 LBL "U" Code: 1 LBL "T" Code: 1 LBL "S" Code: 1 LBL "Q" 

08052018, 08:49 PM
(This post was last modified: 08062018 01:37 AM by Thomas Klemm.)
Post: #2




RE: Periods of Reciprocals of Integers
(12302017 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^k1\). For this to work properly we have to make sure that \(n\) doesn't share divisors with \(10\). Here's a program for the HP41: Code: LBL "PERIOD" This is a translation of the following Python program: Code: def period(n): 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 primefactors of \(n\). Kind regards Thomas 

08062018, 12:59 AM
Post: #3




RE: Periods of Reciprocals of Integers
(08052018 08:49 PM)Thomas Klemm Wrote: There are probably more efficient ways to calculate the smallest integer \(k\) such that \(10^k\equiv1(\mod n)\) since Hi, Thomas, Your code is pretty good. Factoring number is hard. A slight optimization is to check if p==n1 too, and return k+k The code with factoring (factor() not shown) look like this: Code: def order(a, n): # assumed gcd(a, n) = 1 Code: def period(n): 

08062018, 03:37 AM
Post: #4




RE: Periods of Reciprocals of Integers
Meanwhile I've extracted the redundant code into a "function" reduce:
Code: LBL "PERIOD" If you want to also display the digits you can include the following lines: Code: RCL X ; 10*p 10*p 1 However the result isn't correct for values divisible by 2 or 5. (08062018 12:59 AM)Albert Chan Wrote: A slight optimization is to check if p==n1 too, and return k+k Fair point. But we'd still have to run to \(2k\) if we wanted to display the digits. (12302017 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 

08062018, 02:05 PM
Post: #5




RE: Periods of Reciprocals of Integers
(08062018 03:37 AM)Thomas Klemm Wrote:(08062018 12:59 AM)Albert Chan Wrote: A slight optimization is to check if p==n1 too, and return k+k Hi, Thomas: If p==n1 exist, you can deduce the other half digits with 9complements 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)(10001) = 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 

08062018, 05:30 PM
Post: #6




RE: Periods of Reciprocals of Integers
(08062018 02:05 PM)Albert Chan Wrote: If p==n1 exist, you can deduce the other half digits with 9complements Yes, I know. But where do you want to keep the digits once the period is longer than what the limited memory allows us to store? I was afraid that we don't gain much by this optimisation. Feel free to prove me wrong. I'd be interested to see an implementation. Kind regards Thomas PS: I'd rather have my current solution display the digits as well in case of \(n\) having a common divisor with 10. That would be a requirement of Macumazahn's original post. 

08062018, 07:41 PM
Post: #7




RE: Periods of Reciprocals of Integers
I wrongly assumed the half digits had written down. Sorry.
For n != 3,6,9, here is an idea: Instead of searching period and building digits 1 at a time, why not in pairs ? Multiply by 100 instead of 10, stop if reminder = 1, or 10 (1 digit passed period) Here is the search for period(n = 17): 1) 100/17 = 05 + 15/17 2) 1500/17 = 88 + 4/17 3) 400/17 = 23 + 9/17 4) 900/17 = 52 + 16/17 5) 1600/17 = 94 + 2/17 6) 200/17 = 11 + 13/17 7) 1300/17 = 76 + 8/17 8) 800/17 = 47 + 1/17 < stop, remainder = 1, thus period = 2*8 = 16 1/17 = 0.05 88 23 52 94 11 76 47 Unlike my previous optimization, this always cut search steps in half. Also, it showed repeating decimals pairs without storing them. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)