## Finding the prefix length of a decimal expansion

Remember from my previous post that we’re trying to find the prefix length $k$ and repetend length $n$ of the decimal expansion of a fraction $a/b$, that is, the length of the part before it starts repeating, and the length of the repeating part. In that post I showed how to reduce it to the following question:

What are the smallest values of $k$ and $n$ such that $10^k \cdot (10^n - 1)$ is evenly divisible by $b$?

and I left it at that, with some questions for thought.

• Can you see why we get to determine the values of $k$ and $n$ separately, i.e. neither value influences the other at all?

The reason we get to consider $k$ and $n$ separately is that $10^k$ and $(10^n - 1)$ cannot possibly share any prime factors in common. $10^k = 2^k 5^k$ only has 2 and 5 as prime factors; on the other hand, $(10^n - 1)$ cannot have 2 or 5 as prime factors since it is equivalent to $(-1) \bmod 2$ and $\bmod 5$. So the original question splits into two independent questions: (1) What is the smallest value of $k$ such that $10^k$ cancels all the factors of $2$ and $5$ in $b$? (2) What is the smallest value of $n$ such that $(10^n - 1)$ cancels all the other prime factors in $b$?

The first sub-question is easy enough to answer: if $b = 2^x 5^y b'$, where $b'$ has no factors of $2$ or $5$, then choosing $k = \max(x, y)$ is both necessary and sufficient: it will be just enough to cancel all the factors of $2$ and $5$ in $b$.

Let’s see how this works. The example we looked at last time was $\displaystyle 89/420 = 0.21\overline{190476}$. If we factor $420$ we get $(2^2 \cdot 5) \cdot (3 \cdot 7)$, so our analysis above says $k = 2$, since there are two factors of $2$. And sure enough, the decimal expansion has a prefix of length $2$.

As another example, let’s pick a denominator by its factorization: suppose we have a denominator of $2^2 \cdot 5^4 \cdot 11 \cdot 19 \cdot 37 = 19332500$. 5 has a higher exponent than the 2, so we predict the prefix will have length 4: and sure enough, for example,

$\displaystyle 1/19332500 = 0.0000\overline{000517263675158412}.$

We can try other numerators too, we just have to make sure they are relatively prime to $19332500$. For example,

$\displaystyle 1500007 / 19332500 = 0.0775\overline{899133583344109659}$.

In my next post I’ll talk about how to find the repetend length!

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in number theory, pattern and tagged , , , , . Bookmark the permalink.

### 3 Responses to Finding the prefix length of a decimal expansion

1. Pavel says:

In the second to last sentence, I think you meant trying other *numerators*, not *denominators*.

• Brent says:

Thanks, fixed!