16
$\begingroup$

Each rational number (fraction) can be written as a decimal periodic number. Is there a method or hint to derive the length of the period of an arbitrary fraction? For example $1/3=0.3333...=0.(3)$ has a period of length 1.

For example: how to determine the length of a period of $119/13$?

$\endgroup$
  • $\begingroup$ I can't find an algorithm that finds the value for a number that isn't prime, i.e. 10 $\endgroup$ – Code Whisperer Jan 13 '18 at 9:11
  • $\begingroup$ See oeis.org/A002371 $\endgroup$ – Watson Dec 2 '18 at 16:31
17
$\begingroup$

Assuming there are no factors of $2,5$ in the denominator, one way is just to raise $10$ to powers modulo the denominator. When you find $-1$ you are halfway done. Taking your example: $10^2\equiv 9, 10^3\equiv -1, 10^6 \equiv 1 \pmod {13}$ so the repeat of $\frac 1{13}$ is $6$ long. It will always be a factor of Euler's totient function of the denominator. For prime $p$, that is $p-1$.

$\endgroup$
  • 1
    $\begingroup$ You have to look for $1$, because sometimes you won't find $-1$. For example: $10^2\equiv 18, 10^3\equiv 16, 10^4 \equiv 37, 10^5 \equiv 1 \pmod {41}$, so the repeat of $\frac 1{41}$ is $5$ long. $\endgroup$ – jcsahnwaldt says GoFundMonica Mar 26 '15 at 5:37
  • $\begingroup$ You assume that 'there are no factors of 2,5 in the denominator' is it actually required? $\endgroup$ – Shamdor May 5 '15 at 7:28
  • 1
    $\begingroup$ I mean, 1/(2^i * 5^j * d') has the same period length as 1/d', right? $\endgroup$ – Shamdor May 5 '15 at 7:46
  • $\begingroup$ That is correct. You will have $\max(i,j)$ non-repeating digits, then the repeat will start $\endgroup$ – Ross Millikan May 5 '15 at 13:48
13
+50
$\begingroup$

This answer seeks to explain why Ross Millikan's answer works, and provides further information on techniques to speed up the process of seeking the period:

Consider the fraction $\frac17$. The decimal expansion of this is $$ \frac17 = 0.\overline{142857} $$ for a period of 6. Now consider what happens when we multiply it by $10^6$: $$ 10^6\times\frac17 = 142857.\overline{142857} $$ Subtracting the original fraction from this gives $$ (10^6-1)\times\frac17 = 142857 $$ And so, we have $$ \frac17 = \frac{142857}{10^6-1} $$ As you can see, the denominator is one less than a power of 10, and the power is the period of the decimal expansion. This is no accident, and works for any fraction - if you can rewrite it in this form, the denominator reveals the period.

Now, rearrange the equation: $$ 10^6-1 = 142857\times 7 $$ So $10^6$ must be one more than a multiple of 7 (or, more generally, $10^n$ must be one more than a multiple of $d$, where $d$ is the denominator of the fraction and $n$ is the period of the decimal expansion) - indeed, it must be the smallest power of 10 (larger than 1) that has this property.

As such, we can use modular arithmetic to look for the period. Since $a\times d\equiv 0 \pmod d$, we have that $10^n-1\equiv0 \pmod d$, or $$10^n \equiv 1\pmod d$$ And therefore you can just look for the smallest $n>0$ satisfying this.

Of course, there are other approaches to gain the same result, but they're all fundamentally variants of the same idea. That said, if you can factor $\phi(d)$ - the euler totient function of the denominator - then you can accelerate the process of looking for the smallest $n$. For example, when checking 13, you have $\phi(13)=12$, so $n\in\{1,2,3,4,6,12\}$ (as these are the factors of 12) - this can save you a lot of computation (especially where $\phi(d)$ has only a few large factors and 2).

For example, $\phi(167)=166 = 2\times83$, so $n\in\{1,2,83,166\}$. Therefore, we need to check only these four, and we can do it quite efficiently. Obviously, neither $10$ nor $100=10^2$ are equivalent to 1 mod 167, so we only need to actually check 83. For this we can use binary exponentiation. Note that $83 = 2^6 + 2^4 + 2^1 + 2^0$. So we can write $$\begin{align} 10^{83} &= 10^{2\times(2^5 + 2^3 + 1)}\times 10\\ &= (10^{2^3\times(2^2+1)}\times 10)^2 \times 10\\ &= ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \end{align}$$ So, working in modular arithmetic, we can go $$\begin{align} 10^{83} &\equiv ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \mod 167\\ &\equiv ((100^2\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv ((147\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv (134^{2^3}\times 10)^2\times10\mod167\\ &\equiv (87^{2^2}\times 10)^2\times10\mod167\\ &\equiv (54^2\times 10)^2\times10\mod167\\ &\equiv (77\times 10)^2\times10\mod167\\ &\equiv 102^2\times10\mod167\\ &\equiv 50\times10\mod167\\ &\equiv 166\mod167 \end{align}$$ This is the same as $-1\pmod{167}$, so $n=166$ is the only possible period, and $\frac1{167}$ has a period of 166.

Also note that you don't actually have to expand out the product like that. You can just write the number in binary ($83_{10} = 1010011_2$), then work through the binary digits left-to-right - start with 1, and for each digit, $b$, multiply by $10^b$. Square it after each digit except the last one.

$\endgroup$
3
$\begingroup$

The length of the period is given by the multiplicative order of $10 \pmod q$, where $q$ is your quotient. It is closely related to the discrete logarithm. Wikipedia lists several algorithms that are faster than going through all the powers of ten, which is relevant if you're dealing with very large numbers (hundreds of digits).

$\endgroup$
0
$\begingroup$

First you have to simplify to the lowest integer denominator.

Then, the proof for finiteness of repeating part of the decimal representation involves the pigeonhole principle. When you keep on dividing, at some point you will run into a repeat value for the remainder. Given that the remainders that keep the operation going range from 1 to (denominator-1), the possible number of pigeonholes is (denominator-1) as the number of pigeonholes; so that's your worst possible case scenario - in any base.

The particular cases, as described by the other answers, depend on the base, because the denominator may have a special relationship with the base.

  • e.g., in base 10 fractions over 3 will have one repeating decimal, (3) or (6), as 3 divides 9(=10-1), and the remainder will keep repeating.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.