Signs of periodicity of a fraction in an arbitrary number system?

Question

Python

The essence of the question is that you need to programmatically determine the period of a periodic fraction and output it in the format a, (per) .
The difficulty lies in the fact that the number system is arbitrary and is chosen randomly.
And how can this be applied in the case of a mixed periodic fraction.

Answer 1

When you build a fraction a/b, you have a sequence of remainders:
a_0=a%b, a_1=(a_0*p)%b, a_2=(a_1*p)%b,... where p is the base of the number system. As soon as the two remainders a_x and a_y matched - all the digits between them ((a_x*p)/b, (a_{x+1}*p)/b,...,(a_{y-1}*p)/ b) form a period. How to effectively find the period of such a sequence - look. For small b, it is enough to take an array M with indices from 0 to b-1, and for each calculated remainder, check the cell M[a_y]. If nothing has been written to it yet, write M[a_y]=y. If some x lies there, then the period is found.
There are other ways, without using arrays.

Answer 2

A periodic fraction in one number system can be a number with a finite number of significant digits in another number system.
Is the fraction given an ordinary one? Those. ratio of two numbers? Then everything is easy. Let's take for example 4/3 in the decimal number system.
We find the remainder of dividing the numerator by the denominator - 4% 3 = 1. This number will act as the initial value for us.
1) Store the remainder in an array. We multiply the remainder (do not touch the array) by the base of the number system (we have decimal) - 1 * 10 = 10
2) Find the remainder from dividing the number from step [1] by the denominator - 10% 3 = 1
3) If it is zero, then final fraction. Otherwise, we look for the remainder in the array. If found, then we found a period. Otherwise, take the current balance and go to step [1].