# Integer division: the length of the repetitive sequence after the decimal point

When dividing two integers, there may be an infinite sequence of digits after the decimal point (e.g. in the cases of 1/3, 1/7 etc).

As far as I know, if the two numbers divided are integers, this infinite sequence will be, from some point, a repetition of a some finite sequence (this may be also true to dividing rational numbers and not just integers, but I'm keeping it simple for now).

Take for example 1/7, it is equal to 0.14285714285714285714285714285714...

The sequence repeating itself is 142857, a sequence of length 6.

Another example is 1/31, which is equal to 0.032258064516129032258064516129032...

The sequence repeating itself is 032258064516129, a sequence of length 15.

Some divisions do not immediately start with the repeating sequence, e.g. 3/14 which equals 0.21428571428571428571428571428571... (starting with 2, then followed by repetitions of 142857, a sequence of length 6).

Finally, after this long speech, here comes a question that bothers me for a long time: is it possible to find out the length of the repeating sequence using the 2 numbers being divided?

I'm looking for a function that receives a numerator and a denominator as parameters and returns the length of the repetitive sequence. Examples for input+output:

F(1,7) = 6
F(1,31) = 15
F(3,14) = 6
F(1,3) = 1


Does anyone know if this is possible? And if so - how to achieve it?

-
Art of Problem solving is the appropriate place for this question: artofproblemsolving.com/Forum/index.php. –  David Zureick-Brown Oct 17 '09 at 17:45
@Rax: I think this is an appropriate question. I'm reopening it. –  Anton Geraschenko Oct 17 '09 at 18:51
@Anton: thanks, appreciate it –  Rax Olgud Oct 17 '09 at 19:52

The k-th digit of the decimal expansion of a/b is determined by the value of a*10k modulo b. Specifically, the k-th digit is equal to the number of times b divides 10*(remainder when dividing a*10k by b).

As you start increasing k, a*10k runs over various values of Z/b. Eventually, it has to fall into an infinite cycle, and the length of that cycle is F(a,b).

Suppose for a moment that a=1. Then F(1,b) is the multiplicative order of 10 modulo b. That is, it's the smallest number n such that 10k+n=10k (modulo b) for large values of k (I take large values of k because 10 may not be a unit modulo b ... if you like to think of it that way, this is essentially to get rid of the non-repeating digits at the beginning).

If a≠1, then you have to compute the order of multiplication by 10 in the subgroup of Z/b generated by a.

I don't know of any way to easily compute these orders. Just doing it is about as hard as just doing the division, except that you don't keep track of the quotients, just the remainders.

-

Dividing rational numbers is equivalent to dividing integers.

A fairly nice result is known about how large the period (order) can be. Carmichael's theorem asserts that the order always divides a certain function $\lambda(b)$ which can be quickly computed given the prime factorization of $b$, and this result is best possible in the sense that for every b there exists a base relative to which the period of $\frac{1}{b}$ is exactly $\lambda(b)$. $\lambda$ is determined by the following properties:

• If $b = p^k$ is a power of an odd prime, $\lambda(b) = (p-1) p^{k-1}$.
• If $b = 1, 2, 4$, then $\lambda(b) = 1, 1, 2$. If $b = 2^k$ for $k \ge 3$, $\lambda(b) = 2^{k-2}$.
• If $b, b'$ are relatively prime, then $\lambda(b b') = \text{lcm}(\lambda(b), \lambda(b'))$. For example, $\lambda(21) = \text{lcm}(2, 6) = 6$.

If you're interested in these ideas, you may want to start with the simpler Fermat's little theorem or the totient theorem.

-
So how come F(1,31) equals 15? According to your assertion it should be 30, right? –  Rax Olgud Oct 17 '09 at 19:54
No; all you know that it divides 30. –  Qiaochu Yuan Oct 17 '09 at 21:13

If m, n are relatively prime, then F(m, n) depends only on n. (But the condition that m, n are relatively prime matters; consider that F(7, 21) = 1.) Let g(n) = F(1, n), and we'll compute g(n).

In turn, let n = p1^(a1) p2^(a2) ... pk^(ak) where the pi are distinct primes. Then g(n) is the least common multiple of g(p1^(a1)) , g(p2^(a2)), ..., g(pk^(ak)). For example g(11) = 2 since 1/11 = .090909...; g(41) = 5 since 1/41 = 0.0243902439...; go g(451) = 10.

This web page explains the general theory, and this one explains how you might compute g(n) when n is a prime power.

-

The length of the period of a fraction is indifferent to the numerator unless the numerator and the denominator are not in lowest terms (in which case, reduce them to apply the following method).
However, when they are in lowest terms, take the denominator and factor out all factors of the base you're in, as they change nothing (like 2s and 5s in base 10, 3s and 7s in base 21, etc). Then, the length of the period is equal to n, where n is the smallest integer such that your denominator divides bn-1 (where b is your base). So, for example, 1/7 = 0.142857..., and the smallest 10n-1 such that 7 is a factor is 7 is 106-1 = 999999, and 999999/7 = 142857, which is, incidentally, your repeating portion. The same thing even works for, say, 1/2 -- the smallest n is 0, because 100 - 1 = 0, and all non-zero integers divide 0. This is one of the methods for factoring repunits. Note that n will always be less than the denominator.
Similarly, 1/147 (which is 1/11 in base 10) = 0.0431162355..., and the smallest n such that 7n-1 is a multiple of 11 is 10 (710 - 1 = 282475248, and 282475248 / 11 = 25679568).

Multiplying by a constant does nothing to change the period, though it will change the numbers themselves. Interestingly, though, when the period n is equal to 1 less than the denominator (called "max" periodic length), multiplying the fraction by a constant (other than a multiple of the denominator itself) will actually produce a cycle of the period. 2/7 = 0.285714..., 3/7 = 0.428571..., 4/7 = 0.571428..., etc.

Edit: When you divide by factors of the base, let the whole number by which you divide be f. Then, $\lceil \log_{base}f\rceil$ (ceiling function) is equal to the number of non-repeating places before the repeating portion of the decimal. Thus, 1/6, divided by 2, yields 1/3 (1/6 has the same repeating length as 1/3), and we divided by 2. $\lceil\log_{10}2\rceil$ = 1, and indeed, 1/6 = 1.1(6...), with 1 non-repeating decimal.
Furthermore, for fraction m/n, $\lfloor\log_{base}n\rfloor$ is the number of leading zeroes in the repeating portion of the decimal.

-