4
$\begingroup$

Upon dividing two integers, I would like to programmatically predict the number of decimal places that repeat after the decimal point.

For example in $\frac{1}{3}=0.\overline{3}$, I want to know that the number of repeating digits is $1$.

In $\frac{89}{7}=12.\overline{714285}$, I want to get $6$.

Or in $\frac{1054}{13561}$, there are $665$ repeating digits.

I found these numbers in an empirical way; what I'd like now is a deterministic formula that would return this number:

$f(1,3) = 1$
$f(89,7) = 6$
$f(1054,13561) = 665$

Is there such a formula?


Edit: @ajotatxe made me find some interesting things with his comment:

If the divisor is a prime $p≠2,5$, the number of digits divides $p−1$.

First of all, I noticed that the numerator is totally irrelevant: whatever the numerator, the number of repeating decimals is always the same.

So let's focus on the denominator: if I take the prime $71$, there are 35 repeating digits. If I take the prime $191$, there are 95 repeating digits. So it does indeed divide $p-1$, but it's not always $(p-1)/2$ as I was hoping: for the prime $1571$, there are 1570 repeating digits.

Now back to my example $\frac{x}{13561}$ with 665 repeating digits.

Factored into primes, $13561 = 71 \times 191$.

Now let's multiply the number of repeating digits found for both primes: $35 \times 95 = 3325$. First thing to notice, this number divides $625$, which is the number I'm after.

And $3325/ 625 = 5$, which is the GCD of $35$ and $95$.

I can't figure out a deterministic way yet, but I feel like we're getting somewhere?

$\endgroup$
  • $\begingroup$ I wouldn't necessarily say that you found them through empirical methods. $\endgroup$ – marshal craft Jul 4 '15 at 10:20
  • 1
    $\begingroup$ If the divisor is a prime $p\neq2,5$, the number of digits divides $p-1$. $\endgroup$ – ajotatxe Jul 4 '15 at 10:21
  • $\begingroup$ @marshalcraft I found them using a big number library, dividing to a scale of 1000 decimals, then finding where the string repeats. I wouldn't say this is a very scientific approach. $\endgroup$ – Benjamin Jul 4 '15 at 10:23
  • 1
    $\begingroup$ You could use long division to compute the decimal part. For $\frac{a}{b}$ compute $(\frac{r^{10}}{b})^{-10}$ where $r = a$ $ mod$ $b$. The alogrithm can keep appending decimal points but it essentially repeats this process. Sorry if there is a better way. $\endgroup$ – marshal craft Jul 4 '15 at 10:39
  • 1
    $\begingroup$ The period of the decimal representation of $\frac1n$ is OEIS A007732. There is no nice formula, but the entry does offer a MAPLE algorithm. $\endgroup$ – Brian M. Scott Jul 4 '15 at 20:00
2
$\begingroup$

Your question is not well-defined because some fractions do not have a decimal expansion that consists only of repeating blocks after the decimal place, such as $\frac{1}{6}$. However, if the denominator $d$ is coprime to $10$, then what you are looking for is equivalent to the order of $10$ modulo $d$. In that case, we have reduced this to a previously solved question at Algorithms for finding the multiplicative order of an element in a group of integers mod m.

$\endgroup$
  • $\begingroup$ You make a good point about $\frac{1}{6}$! $\endgroup$ – Benjamin Jul 4 '15 at 11:08
  • $\begingroup$ He has said the answer basically you are looking for smallest integer $k$ such that $10^k=1$ $mod$ $d$. It uses congruence mods hopefully you are familiar with, if not look it up I recommend. If $d$ is prime then it has to be a factor of $d-1$. Unfortunately you will have to at this point simply try the factors. There is no known formula to tell order of a given number mod $p$ for all numbers. $\endgroup$ – marshal craft Jul 4 '15 at 11:42
  • $\begingroup$ @marshalcraft: Smallest positive integer $k$, yes. In general the order divides $φ(d)$. If $d$ is prime, $φ(d) = d - 1$. $\endgroup$ – user21820 Jul 4 '15 at 12:41

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.