7
$\begingroup$

I noticed that WolframAlpha, given an operation like $\frac{n}{m},\;n,m \in N$ that result in a periodic decimal number, computes really fast the length of the period.

E.g. $\frac{3923}{6173}$ has a period of 3086: here.

I was wondering how this computation is done: is there some method to do this (except the trivial one of executing the division and looking for a sequence repetition) ?

$\endgroup$
  • $\begingroup$ Note: i'm not a mathematician, I apologize if I have done some mistake with names, tags, etc.. $\endgroup$ – Aslan986 May 3 '12 at 20:54
5
$\begingroup$

The period is always a factor of the totient of the denominator. In your example, 6173 is prime, so its totient is 6172 and half of that is 3086. I suspect Alpha is just doing the long division. When the remainder at any step matches the remainder at a previous step you have found the repeat. You can also find the repeat by finding the $k$ such that $10^k \equiv 1 \pmod {denominator}$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Suppose that the fraction $\rm\:r\in (0,1)$ has a decimal expansion purely periodic of length $\rm\:k.\:$ Then $\rm\:10^k r - r\:\! =\:\! (10^k-1)\:\! r = n\:$ is an integer, since $\rm\:10^k r\:$ is simply $\rm\:r\:$ left-shifted by $\rm\:k\:$ places, so its digits after the decimal point are the same as those of $\rm\:r,\:$ so they cancel out in the subtraction, leaving an integer. Conversely, if $\rm\: r = n/(10^k-1)$ then $\rm\:10^k\:\! r = n + r\:$ so $\rm\:r\:$ has period $\rm\:k\:$ (or a divisor of $\rm\:k\:$ if the cycle is not minimal).

Therefore, to find the minimal period of $\rm\:r = n/m\:$ we need to find the minimal $\rm\:k\:$ such that $\rm\:(10^k-1) n/m\:$ is an integer, i.e. such that $\rm\:m\:|\:n\:\!(10^k-1)\:$ (here $\rm\:a\:|\:b\:$ denotes $\rm\:a\:$ divides $\rm\:b).\:$ We may assume that $\rm\:n/m\:$ is in lowest terms, i.e. $\rm\:gcd(m,n) = 1.\:$ Hence, by Euclid's lemma, from $\rm\:m\:|\:n\:\!(10^k-1)\:$ we deduce $\rm\:m\:|\:10^k-1.\:$ Thus to find the least period we need to find the least $\rm\:k\:$ such that $\rm\:10^k \equiv 1\pmod{m},\:$ i.e. the order of $10,\:$ modulo $\rm\:m.\:$ There are various algorithms known for computing such orders, e.g. see the references in this post.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ See also here. $\endgroup$ – Gone Feb 17 at 0:16
  • $\begingroup$ What do you mean by "if the cycle is not minimal"? $\endgroup$ – rocksNwaves Feb 17 at 0:53
  • $\begingroup$ Also, I'm trying to understand where you are going with "so r has period k (if the cycle is not minimal". I say this because you established in the first sentence that the period was k. I'm just trying to figure out what added information the quoted statement gives us. $\endgroup$ – rocksNwaves Feb 17 at 0:56
  • 1
    $\begingroup$ @rocksNwaves For example, if it repeats every $3$ digits then it also repeats every $6,9,12,\ldots$ digits too. But we seek the least such period, i.e. the minimal cycle length. $\endgroup$ – Gone Feb 17 at 1:03
0
$\begingroup$

consider for example $10/3=0.333333333333333 $ which has period 3,or 33 or as you like,it happens when one number can't be divided by another exactly and during this division,some sequence of numbers is repeating

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yes, sure :).The period length here is 1. In the example above the period length is 3086. I mean, 3086 is not the period, but it is its length. I Wonder how to compute this length a priori. $\endgroup$ – Aslan986 May 3 '12 at 21:11

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.