A recurring number is generated by dividing two whole numbers to obtain a decimal whose digits after the point never end. For example, if we divide 1 by 3, we'll get 0.333333333... Remember that division works by dividing a number by the next digit, writing the whole number result as a digit of the answer and using the remainder as a carry, like so:
1 can be written as 1.00000..., which is what we'll do. \------------ 3/1 . 0 0 0 0 1 divided by 3 is 0 remainder 1, so we write 0 above and put 1 as a carry on the next digit. 0 \----------- 3/1 . 10 0 0 10 divided by 3 is 3 remainder 1, so we write 3 above and put 1 as a carry on the next digit. 0 . 3 \------------ 3/1 . 10 10 0 10 divided by 3 is 3 remainder 1, so we write 3 above and put 1 as a carry on the next digit. 0 . 3 3 \------------- 3/1 . 10 10 10 and so on.
But recurring numbers can sometimes be less simple, such as 1/7 which is 0.142857142857142857...:
1 can be written as 1.00000..., which is what we'll do. \------------ 7/1 . 0 0 0 0 0 \----------- 7/1 . 10 0 0 0 . 1 \------------ 7/1 . 10 30 0 ... 0 . 1 4 2 8 5 7 \------------------------- 7/1 . 10 30 20 60 40 50 10 ... 0 . 1 4 2 8 5 7 1 4 2 8 5 7 \------------------------------------------- 7/1 . 10 30 20 60 40 50 10 30 20 60 40 50 10
So why does this happen? Why don't the digits kept changing differently but instead start repeating a sequence? It's because the next digit depends on what remainder the previous digit left, so if the previous digit left a remainder which was left by another previous digit then the new digit and new remainder will be the same as the earlier digit. For example, in this case, the remainder was a 1, but the first remainder left was also a 1, so the sequence will repeat itself:
0 . 1 4 2 8 5 7 \------------------------- 7/1 . 10 30 20 60 40 50 10 0 . 1 4 2 8 5 7 1 \------------------------- 7/1 . 10 30 20 60 40 50 10 0 . 1 4 2 8 5 7 1 4 \--------------------------- 7/1 . 10 30 20 60 40 50 10 30 ... 0 . 1 4 2 8 5 7 1 4 2 8 5 7 \------------------------------------------- 7/1 . 10 30 20 60 40 50 10 30 20 60 40 50 10
More technically, this is because the digits are generated using a finite state, the remainder, and when you try to generate an infinite sequence using a finite state, eventually you must get repetition, since you must reuse a previously used state at some point in the infinite sequence.
We can draw this idea using a finite state automaton where the states are the remainders left by a digit and the transition gives the next digit. For example, this is what the finite state automaton for 1/7 is:
Remember, the numbers in the circles are remainders, which are used as carries in front of zeros, and the numbers on the arrows are digits in the result. So we start from a remainder of 1 which results from when we start dividing 1 by 7, and start jumping from remainder to remainder. Now we can either end up with a remainder of 0, in which case the result would terminate and will not be recurring, or it will jump to a remainder which has already been traversed, in which case it will enter an infinite loop, which results in a recurring number. As the transitions show, in the case of dividing by 7, the second case is inevitable, regardless of which non-zero remainder we start with.
Since every number can leave only one of a finite number of remainders when used to divide another number, the result can either be a terminating number or a recurring number and cannot keep on changing forever. Further more, since the number of remainders a number can leave when divided is equal to that number (x/2 can only leave either 0 or 1 as remainders, x/3 can only leave either 0, 1 or 2 as remainders, etc) then there can only be that number of remainders. Since there can only be that number of remainders, and since a remainder of 0 would terminate the number, then the length of the recurring part of a number cannot be longer than one less than the denominator of that number. For example, for all x, x/7 cannot have a recurring part longer than 6 digits. Likewise, for all x, x/100 cannot have a recurring part longer than 99 digits.
Notice that the finite state automaton as used here only works for when we start adding zeros after the point during division. For example, if we divide the following:
\-------------------- 7/1 . 1 2 3 0 0 0
then the finite state automaton can only be used when we start using the zeros at the end since the numbers in the automaton assume that the remainders are carried on to zeros. Since even if we use another recurring number, that recurring number can be converted to a fraction and the quotient of two fractions is another fraction, then the finite state automaton can also be used on recurring numbers. For example, if we divide the following:
\-------------------- 7/0 . 3 3 3 3 3 3 ...
then we can convert 0.3333... into 1/3, the division can be converted to the fraction (1/3)/7 which can be simplified to 1/(3x7) = 1/21. Now we can use the finite state automaton on 1/21 and reason on when the result should start recurring.
Finally we see that if we divide an irrational number then the result could also be irrational since the state is not finite anymore but will be changing forever with every digit in the divided number.
This is the basis for the finite state automata's pumping lemma, which says that if the number of letters (or digits in this case) generated from a finite state automaton exceeds the number or states in the automaton, then there must be reuse of a previously visited state and thus the letters cannot be forever randomly generated but must follow a regular pattern at that point. In this case we have an even stronger pumping lemma which says that not only will the digits follow a regular pattern after exceeding the number of states in the automaton but will forever repeat the same sequence. This is because there is only one transition going out of each state since only one remainder can be left when dividing a number, so once a state is revisited there is no other path to follow except the previously visited path.
No comments:
Post a Comment