Thoughts on 1/7 and other rational numbers (Part 7)

In a previous post concerning roundoff error, I mentioned that the number $1/10$ equals

$\displaystyle \frac{1}{2^4} + \frac{1}{2^5} +\frac{1}{2^8} + \frac{1}{2^9} + \frac{1}{2^{12}} + \frac{1}{2^{13}} + \dots$

In other words, the binary expansion of $1/10$ is

$0.0001100110011001100110011001100....$

That’s the expansion of the fraction in base $2$ , as opposed to base $10$ .

In the previous post, I verified that the above infinite series actually converges to $1/10$ :

$S = \displaystyle \left(\frac{1}{2^4} + \frac{1}{2^5}\right) +\left(\frac{1}{2^8} + \frac{1}{2^9}\right) + \left(\frac{1}{2^{12}} + \frac{1}{2^{13}}\right) + \dots$

$S = \displaystyle \frac{3}{2^5} + \frac{3}{2^9} + \frac{3}{2^{13}} + \dots$

$S = \displaystyle \frac{\displaystyle \frac{3}{2^5}}{\quad \displaystyle 1 - \frac{1}{2^4} \quad}$

$S = \displaystyle \frac{\displaystyle \frac{3}{32}}{\quad \displaystyle \frac{15}{16} \quad}$

$S = \displaystyle \frac{3}{32} \times \frac{16}{15}$

$S = \displaystyle \frac{1}{10}$

Still, a curious student may wonder how one earth one could directly convert $1/10$ into binary without knowing the above series ahead of time.

This can be addressed by using the principles that we’ve gleaned in this study of decimal representations, except translating this work into the language of base $2$ . In the following, I will use the subscripts $\hbox{ten}$ and $\hbox{two}$ so that I’m clear about when I’m using decimal and binary, respectively.

To begin, we note that $10_{\hbox{\scriptsize ten}} = 1010_{\hbox{\scriptsize two}} = 10_{\hbox{\scriptsize two}} \times 101_{\hbox{\scriptsize two}}$ . (In other words, ten is equal to two times five.) So, following Case 3 of the previous post, we will attempt to write the denominator in the form

$10_{\hbox{\scriptsize two}}^d \left(10_{\hbox{\scriptsize two}}^k - 1 \right)$ , or $2_{\hbox{\scriptsize ten}}^d \left(2_{\hbox{\scriptsize ten}}^k - 1 \right)$

If $k = 1_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^1 - 1 = 1_{\hbox{\scriptsize ten}}$ , but $1_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 2_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^2 - 1 = 3_{\hbox{\scriptsize ten}}$ , but $3_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 3_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^3 - 1 = 7_{\hbox{\scriptsize ten}}$ , but $7_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}}$ is not an integer.
If $k = 4_{\hbox{\scriptsize ten}}$ , then $2_{\hbox{\scriptsize ten}}^4 - 1 = 15_{\hbox{\scriptsize ten}}$ . This time, $15_{\hbox{\scriptsize ten}} \div 5_{\hbox{\scriptsize ten}} = 3_{\hbox{\scriptsize ten}}$ . Written in binary,

$101_{\hbox{\scriptsize two}} \times 11_{\hbox{\scriptsize two}} = 1111_{\hbox{\scriptsize two}}$

We now return to the binary representation of $1/10_{\hbox{\scriptsize ten}} = 1/1010_{\hbox{\scriptsize two}}$ .

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = \displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} \times \frac{11_{\hbox{\scriptsize two}}}{11_{\hbox{\scriptsize two}}}$

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = \frac{11_{\hbox{\scriptsize two}}}{11110_{\hbox{\scriptsize two}}}$

Therefore, the binary representation has a delay of one digit and a repeating block of four digits:

$\displaystyle \frac{1}{1010_{\hbox{\scriptsize two}}} = 0.0\overline{0011}$

Naturally, this matches the binary representation given earlier.

Thoughts on 1/7 and other rational numbers (Part 6)

In Part 5 of this series, I showed that fractions of the form $\displaystyle \frac{M}{10^d}$ , $\displaystyle \frac{M}{10^k - 1}$ , and $\displaystyle \frac{M}{10^d (10^k-1)}$ can be converted into their decimal representations without using long division and without using a calculator.

The amazing thing is that every rational number $\displaystyle \frac{a}{b}$ can be written in one of these three forms. Therefore, after this conversion is made, then the decimal expansion can be found without a calculator.

Case 1. If the denominator $b$ has a prime factorization of the form $2^m 5^n$ , then $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^d}$ , where $d = \max(m,n)$ .

For example,

$\displaystyle \frac{3}{160} = \displaystyle \frac{3}{2^5 \times 5}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{3}{2^5 \times 5} \times \frac{5^4}{5^4}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{3 \times 5^4}{2^5 \times 5^5}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{1875}{10^5}$

$\displaystyle \frac{3}{160} = 0.01875$

The step of multiplying both sides by $\displaystyle \frac{5^4}{5^4}$ is perhaps unusual, since we’re so accustomed to converting fractions into lowest terms and not making the numerators and denominators larger. This particular form of $1$ was chosen in order to get a power of $10$ in the denominator, thus facilitating the construction of the decimal expansion.

Case 2. If the denominator $b$ is neither a multiple of $2$ nor $5$ , then $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^k - 1}$ .

For example,

$\displaystyle \frac{3}{11} = \displaystyle \frac{3}{11} \times \frac{9}{9}$

$\displaystyle \frac{3}{11} = \displaystyle \frac{27}{99}$

$\displaystyle \frac{3}{11} = 0.\overline{27}$

This example wasn’t too difficult since we knew that $9 \times 11 = 99$ . However, finding the smallest value of $k$ that works can be a difficult task requiring laborious trial and error.

However, we do have a couple of theorems that can assist in finding $k$ . First, since $k$ is the length of the repeating block, we are guaranteed that $k$ must be less than the denominator $b$ since, using ordinary long division, the length of the repeating block is determined by how many steps are required until we get a remainder that was seen before.

However, we can do even better than that. Using ideas from number theory, it can be proven that $k$ must be a factor of $\phi(b)$ , which is the Euler toitent function or the number of integers less than $b$ that are relatively prime with $b$ . In the example above, the denominator was $11$ , and clearly, if $1 \le n < 11$ , then $\gcd(n,11) = 1$ . Since there are $10$ such numbers, we know that $k$ must be a factor of $10$ . In other words, $k$ must be either $1$ , $2$ , $5$ , or $10$ , thus considerably reducing the amount of guessing and checking that has to be done. (Of course, for the example above, $k=2$ was the least value of $k$ that worked.)

In general, if $n = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r}$ is the prime factorization of $n$ , then

$\phi(n) = n \left( \displaystyle 1 - \frac{1}{p_1} \right) \left( \displaystyle 1 - \frac{1}{p_2} \right) \dots \left( \displaystyle 1 - \frac{1}{p_r} \right)$

For the example above, since $11$ was prime, we have $\phi(11) = 11 \left( \displaystyle 1 - \frac{1}{11} \right) = 10$ .

Case 3. Suppose the prime factorization of the denominator $b$ both (1) contains $2$ and/or $5$ and also (2) another prime other than $2$ and $5$ . This is a mixture of Cases 1 and 2, and the fraction $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^d (10^k-1)}$ .

For example, consider

$\displaystyle \frac{11}{74} = \displaystyle \frac{11}{2 \times 37}$

Following the rule for Case 1, we should multiply by $\displaystyle \frac{5}{5}$ to get a $10$ in the denominator:

$\displaystyle \frac{11}{74} = \displaystyle \frac{11}{2 \times 37} \times \frac{5}{5} = \frac{55}{10 \times 37}$

Next, we need to multiply $37$ by something to get a number of the form $10^k - 1$ . Since $37$ is prime, every number less than $37$ is relatively prime with $37$ , so $\phi(37) = 36$ . Therefore, $k$ must be a factor of $36$ . So, $k$ must be one of $1$ , $2$ , $3$ , $4$ , $6$ , $9$ , $12$ , $18$ , and $36$ .

(Parenthetically, while we’ve still got some work to do, it’s still pretty impressive that — without doing any real work — we can reduce the choices of $k$ to these nine numbers. In that sense, the use of $\phi(n)$ parallels how the Rational Root Test is used to determine possible roots of polynomials with integer coefficients.)

So let’s try to find the least value of $k$ that works.

If $k = 1$ , then $10^1 - 1 = 9$ , but $9 \div 37$ is not an integer.
If $k = 2$ , then $10^2 - 1 = 99$ , but $99 \div 37$ is not an integer.
If $k = 3$ , then $10^3 - 1 = 999$ , and it turns out that $999 \div 37 = 27$ , an integer.

Therefore,

$\displaystyle \frac{11}{74} = \frac{55}{10 \times 37} \times \frac{27}{27}$

$\displaystyle \frac{11}{74} = \frac{1485}{10 \times 999}$

$\displaystyle \frac{11}{74} = \frac{999 + 486}{10 \times 999}$

$\displaystyle \frac{11}{74} = \frac{999}{10 \times 999}+ \frac{486}{10 \times 999}$

$\displaystyle \frac{11}{74} = \frac{1}{10}+ \frac{486}{10 \times 999}$

$\displaystyle \frac{11}{74} = 0.1 + 0.0\overline{486}$

$\displaystyle \frac{11}{74} = 0.1\overline{486}$

Thoughts on 1/7 and other rational numbers (Part 5)

Students are quite accustomed to obtaining the decimal expansion of a fraction by using a calculator. Here’s an (uncommonly, I think) taught technique for converting certain fractions into a decimal expansion without using long division and without using a calculator. I’ve taught this technique to college students who want to be future high school teachers for several years, and it never fails to surprise.

First off, it’s easy to divide any number by a power of $10$ , or $10^k$ . For example,

$\displaystyle \frac{4312}{1000} = 4.312$ and $\displaystyle \frac{71}{10000} = 0.00071$

What’s less commonly known is that it’s also easy to divide by $10^k - 1$ , or $99\dots 9$ , a numeral with $k$ consecutive $9$ s. (This number can be used to prove the divisibility rules for 3 and 9 and is also the subject of one of my best math jokes.) The rule can be illustrated with a calculator:

In other words, if $M < 10^k - 1$ , then the decimal expansion of $\displaystyle \frac{M}{10^k-1}$ is a repeating block of $k$ digits containing the numeral $M$ , possibly adding enough zeroes to fill all $k$ digits.

To prove that this actually works, we notice that

$\displaystyle \frac{M}{10^k - 1} = M \times \frac{ \displaystyle \frac{1}{10^k}}{\quad \displaystyle 1 - \frac{1}{10^k} \quad}$

$\displaystyle \frac{M}{10^k - 1} = M \times \left(\displaystyle \frac{1}{10^k} + \frac{1}{10^{2k}} + \frac{1}{10^{3k}} + \dots \right)$

$\displaystyle \frac{M}{10^k-1} = M \times 0.\overline{00\dots01}$

The first line is obtained by multiplying the numerator and denominator by $\displaystyle \frac{1}{10^k}$ . The second line is obtained by using the formula for an infinite geometric series in reverse, so that the first term is $\displaystyle \frac{1}{10^k}$ and the common ratio is also $\displaystyle \frac{1}{10^k}$ . The third line is obtained by converting the series — including only powers of $10$ — into a decimal expansion.

If $M > 10^k - 1$ , then the division algorithm must be used to get a numerator that is less than $10^k-1$ . Fortunately, dividing big numbers by $10^k-1$ is quite easy and can be done without a calculator. For example, let’s find the decimal expansion of $\displaystyle \frac{123456}{9999}$ without a calculator. First,

$123456 = 12(10000) + 3456$

$123456 = 12(9999 + 1) + 3456$

$123456 = 12(9999) + 12(1) + 3456$

$123456 = 12(9999) + 3468$

Therefore,

$\displaystyle \frac{123456}{9999} = \displaystyle \frac{12(9999) + 3468}{9999}$

$\displaystyle \frac{123456}{9999} = \displaystyle \frac{12(9999)}{9999} + \frac{3468}{9999}$

$\displaystyle \frac{123456}{9999} = \displaystyle 12 + \frac{3468}{9999}$

$\displaystyle \frac{123456}{9999} = \displaystyle 12.\overline{3468}$

This can be confirmed with a calculator. Notice that the repeating block doesn’t quite match the digits of the numerator because of the intermediate step of applying the division algorithm.

In the same vein, it’s also straightforward to find the decimal expansion of fractions of the form $\displaystyle \frac{M}{10^d (10^k-1)}$ , so that the denominator has the form $99\dots9900\dots00$ . This is especially easy if $M < 10^k -1$ . For example,

$\displaystyle \frac{123}{99900} = \frac{1}{100} \times \frac{123}{999} = \frac{1}{100} \times 0.\overline{123} = 0.00\overline{123}$

On the other hand, if $M > 10^k-1$ , then the division algorithm must be applied as before. For example, let’s find the decimal expansion of $\displaystyle \frac{51237}{99000}$ . To begin, we need to divide the numerator by $99$ , as before. Notice that, for this example, an extra iteration of the division algorithm is needed to get a remainder less than $99$ .

$51237 = 512(100) + 37$

$51237 = 512(99 + 1) + 37$

$51237 = 512(99) + 512 + 37$

$51237 = 512(99) + 549$

$51237= 512(99) + 5(100) + 49$

$51237 = 512(99) + 5(99 + 1) + 49$

$51237 = 512(99) + 5(99) + 5 + 49$

$51237 = 517(99) + 54$

Therefore,

$\displaystyle \frac{51237}{99000} = \displaystyle \frac{517(99) + 54}{99000}$

$\displaystyle \frac{51237}{99000} = \displaystyle \frac{517(99)}{99000} + \frac{54}{99000}$

$\displaystyle \frac{51237}{99000} = \displaystyle \frac{517}{1000} + \frac{54}{99000}$

$\displaystyle \frac{51237}{99000} = 0.517 + 0.000\overline{54}$

$\displaystyle \frac{51237}{99000} = 0.517\overline{54}$

In particular, notice that the three $0$ s in the denominator correspond to a delay of length 3 (the digits $517$ ), while the $99 = 10^2 - 1$ in the denominator corresponds to the repeating block of length $2$ .

These can be confirmed for students who may be reluctant to believe that decimal expansions can be found without a calculator.

Thoughts on 1/7 and other rational numbers (Part 4)

In Part 3 of this series, I considered the conversion of a repeating decimal expansion into a fraction. This was accomplished by an indirect technique which was pulled out of the patented Bag of Tricks. For example, if $x = 0.\overline{432} = 0.432432432\dots$ , we start by computing $1000x$ and then subtracting.

$1000x = 432.432432\dots$

$x = 0.432432\dots$

$999x = 432$

$x = \displaystyle \frac{432}{999} = \displaystyle \frac{16}{37}$

As mentioned in Part 3, most students are a little bit skeptical that this actually works, and often need to type the final fraction into a calculator to be reassured that the method actually works. Most students are also a little frustrated with this technique because it does come from the Bag of Tricks. After all, the first two steps (setting the decimal equal to $x$ and then multiplying $x$ by $1000$ ) are hardly the most intuitive things to do first… unless you’re clairvoyant and know what’s going to happen next.

In this post, I’d like to discuss a more direct way of converting a repeating decimal into a fraction. In my experience, this approach presents a different conceptual barrier to students. This is a more direct approach, and so students are more immediately willing to accept its validity. However, the technique uses the formula for an infinite geometric series, which (unfortunately) most senior math majors cannot instantly recall. They’ve surely seen the formula before, but they’ve probably forgotten it because a few years have passed since they’ve had to extensively use the formula.

Anyway, here’s the method applied to $0.\overline{432}$ . To begin, we recall the meaning of a decimal representation in the first place:

$0.432432432 \dots = \displaystyle \frac{4}{10} + \frac{3}{100} + \frac{2}{1000} + \displaystyle \frac{4}{10^4} + \frac{3}{10^5} + \frac{2}{10^6} + \displaystyle \frac{4}{10^7} + \frac{3}{10^8} + \frac{2}{10^9} + \dots$

Combining fractions three at a time (matching the length of the repeating block), we get

$0.432432432 \dots = \displaystyle \frac{432}{10^3} + \displaystyle \frac{432}{10^6} + \frac{432}{10^9} + \dots$

This is an infinite geometric series whose first term is $\displaystyle \frac{432}{10^3}$ , and the common ratio that’s multiplied to go from one term to the next is $\displaystyle \frac{1}{10^3}$ . Using the formula for an infinite geometric series and simplifying, we conclude

$0.432432432 \dots = \displaystyle \frac{ \quad \displaystyle \frac{432}{1000} \quad }{\quad 1 - \displaystyle \frac{1}{1000} \quad}$

$0.432432432 \dots = \displaystyle \frac{ \displaystyle \quad \frac{432}{1000} \quad}{ \displaystyle \quad \frac{999}{1000} \quad}$

$0.432432432 \dots = \displaystyle \frac{ 432}{ 999}$

$0.432432432 \dots = \displaystyle \frac{ 16}{ 37}$

For what it’s worth, the decimal representation could have been simplified by using three separate geometric series. Some students find this to be more intuitive, combining the unlike fractions at the final step as opposed to the initial step.

$0.432432432 \dots = \left( \displaystyle \frac{4}{10} + \frac{4}{10^4} + \displaystyle \frac{4}{10^7} + \dots \right)$

$\quad \quad \quad \quad + \left( \displaystyle \frac{3}{100} + \frac{3}{10^5} + \displaystyle \frac{3}{10^8} + \dots \right)$

$+ \left( \displaystyle \frac{2}{1000} + \frac{2}{10^6} + \displaystyle \frac{2}{10^9} + \dots \right)$

$0.432432432 \dots = \displaystyle \frac{ \quad \displaystyle \frac{4}{10} \quad }{\quad 1 - \displaystyle \frac{1}{1000} \quad} + \frac{ \quad \displaystyle \frac{3}{100} \quad }{\quad 1 - \displaystyle \frac{1}{1000} \quad} + \frac{ \quad \displaystyle \frac{2}{1000} \quad }{\quad 1 - \displaystyle \frac{1}{1000} \quad}$

$0.432432432 \dots = \displaystyle \frac{ \quad \displaystyle \frac{4}{10} \quad }{\quad \displaystyle \frac{999}{1000} \quad} + \frac{ \quad \displaystyle \frac{3}{100} \quad }{\quad \displaystyle \frac{999}{1000} \quad} + \frac{ \quad \displaystyle \frac{2}{1000} \quad }{\quad \displaystyle \frac{999}{1000} \quad}$

$0.432432432 \dots = \displaystyle \frac{ 400}{ 999} + \frac{30}{999} + \frac{2}{999}$

$0.432432432 \dots = \displaystyle \frac{ 432}{ 999}$

$0.432432432 \dots = \displaystyle \frac{ 16}{ 37}$

Finally, this direct technique also works for repeating decimals with a delay, like $0.41\overline{6}$ .

$0.41666\dots = \displaystyle \frac{4}{10} + \frac{1}{100} + \left( \frac{6}{1000} + \frac{6}{10^4} + \frac{6}{10^5} + \dots \right)$

$0.41666\dots = \displaystyle \frac{4}{10} + \frac{1}{100} + \displaystyle \frac{ \quad \displaystyle \frac{6}{1000} \quad }{\quad 1 - \displaystyle \frac{1}{10} \quad}$

$0.41666\dots = \displaystyle \frac{4}{10} + \frac{1}{100} +\displaystyle \frac{ \quad \displaystyle \frac{6}{1000} \quad }{\quad \displaystyle \frac{9}{10} \quad}$

$0.41666\dots = \displaystyle \frac{4}{10} + \frac{1}{100} +\frac{6}{900}$

$0.41666\dots = \displaystyle \frac{375}{900}$

$0.41666\dots = \displaystyle \frac{5}{12}$

Thoughts on 1/7 and other rational numbers (Part 3)

In Part 2 of this series, I discussed the process of converting a fraction into its decimal representation. In this post, I consider the reverse: starting with a decimal representation, and ending with a fraction.

Let me say at the onset that the process I’m about to describe appears to be a dying art. When I show this to my math majors who want to be high school teachers, roughly half have either not seen it before or else have no memory of seeing it before. (As always, I hold my students blameless for the things that they were simply not taught at a younger age, and part of my job is repairing these odd holes in their mathematical backgrounds so that they’ll have their best chance at becoming excellent high school math teachers.) I’m guessing that this algorithm is a dying art because of the ease and convenience of modern calculators.

So let me describe how I describe this procedure to my students. To begin, suppose that we’re given a repeating decimal like $0.\overline{432} = 0.432432432\dots$ . How do we change this into a decimal? Let’s call this number $x$ .

I’m now about to do something that, if you don’t know what’s coming next, appears to make no sense. I’m going to multiply $x$ by $1000$ . Students often give skeptical, quizzical, and/or frustrated looks about this non-intuitive next step… they’re thinking, “How would I ever have thought to do that on my own?” To allay these concerns, I explain that this step comes from the patented Bag of Tricks. Socrates gave the Bag of Tricks to Plato, Plato gave it to Aristotle, it passed down the generations, my teacher taught the Bag of Tricks to me, and I teach it to my students. Multiplying by $1000$ on the next step is absolutely not obvious, unless you happen to know via clairvoyance what’s going to come next.

Anyway, let’s write down $x$ and also $1000x$ .

$1000x = 432.432432\dots$

$x = 0.432432\dots$

Notice that the decimal parts of both $x$ and $1000x$ are the same. Subtracting, the decimal parts cancel, leaving

$999x = 432$

$x = \displaystyle \frac{432}{999} = \displaystyle \frac{16}{37}$

In my experience, most students — even senior math majors who have taken a few theorem-proof classes and hence are no dummies — are a little stunned when they see this procedure for the first time. To make this more real and believable to them, I then ask them to pop out their calculators to confirm that this actually worked. (Indeed, many students need this confirmation to be psychologically sure that it really did work.)

Then I ask my students, why did we multiply by $1000$ ? They’ll usually give the correct answer: so that the decimal parts will cancel. My follow-up question is, what should we do if the decimal is $0.\overline{24}$ ? They’ll usually respond that we should multiply by $100$ or, in general, by $10^n$ , where $n$ is the length of the repeating block.

This strategy, of course, works for $0.\overline{142857}$, eventually yielding

$0.\overline{142587} = \displaystyle \frac{142857}{999999} = \displaystyle \frac{1}{7}$

after cancellation.

The same procedure works for decimal expansions with a delay, like $x = 0.72\overline{3}$ . This time, I’ll ask them how we should go about changing this into a fraction. I usually get at least one of three responses. I love getting multiple responses, as this gives the students a chance to came the “different” answers, compare the different strategies, and

Answer #1. Multiply $x$ by $1000$ since the repeating pattern starts at the 3rd decimal place.

$1000x = 723.333\dots$

$x = 0.7233\dots$

$\therefore 999x = 722.61$

$x =\displaystyle\frac{722.61}{999} = \displaystyle\frac{72261}{99900} = \displaystyle \frac{217}{300}$

Answer #2. Multiply $x$ by $10$ since the repeating block has length 1.

$10x = 7.23333\dots$

$x = 0.7233\dots$

$\therefore 9x = 6.51$

$x = \displaystyle \frac{6.51}{9} = \displaystyle\frac{651}{900} = \displaystyle\frac{217}{300}$

Answer #3. First multiply $x$ by 100 to get rid of the delay. Then multiply $100 x$ by an extra $10$ since the repeating block has length 1.

$1000x = 723.333\dots$

$100x = 72.33\dots$

$\therefore 900x = 651$

$x = \displaystyle\frac{651}{900} = \displaystyle\frac{217}{300}$

The above discussion concerned repeating decimals. For completeness, converting terminating decimals into a fraction is easy. For example,

$0.124 = \displaystyle \frac{1}{10} + \frac{2}{100} + \frac{4}{1000} = \displaystyle \frac{124}{1000} = \displaystyle \frac{31}{250}$

One more thought. The concept behind Part 2 of this series shows that a rational number of the form $k/n$ , where both $k$ and $n$ are integers, must have either a terminating decimal expansion or else a repeating decimal expansion (possibly with a delay). In this post, we went the other direction. Therefore, we have the basis for the following theorem.

Theorem. A number $x$ is rational if and only if it has either a terminating decimal expansion or else a repeating decimal expansion.

The contrapositive of this theorem is perhaps intuitively obvious.

Theorem. A number $x$ is irrational if and only if it has a non-terminating and non-repeating decimal expansion.

In my experience, most students absolutely believe both of these theorems. For example, most students believe that $\sqrt{2}$ has a decimal expansion that neither terminates nor repeats. That said, most math majors are surprised to discover that it does take quite a bit of work — like a formal write-up of Parts 2 and 3 of this series — to actually prove this statement from middle-school mathematics.

Thoughts on 1/7 and other rational numbers (Part 2)

Let’s take another look at the decimal expansion of 1/7:

This result from a calculator should convince most students that $\displaystyle \frac{1}{7} = 0.\overline{142857}$ . After all, there’s a second $142$ after the first $7$ , and the ending $9$ is consistent with rounding up the $857$ .

So the evidence that $\displaystyle \frac{1}{7} = 0.\overline{142857}$ is persuasive.

But does this prove beyond a shadow of a doubt that this decimal representation is correct?

Sadly, no. Taken by itself, the result of the calculator is also consistent with, to give just one example, $\displaystyle \frac{1}{7} = 0.\overline{142857142910235}$ , which also would truncate after 10 decimal places to the result shown above.

In short, the calculator gives evidence that the decimal expansion is correct, but does not prove that it’s correct.

Which leads to the obvious question: how do we prove it?

One method, which used to be taught in elementary school (I honestly don’t know if this is taught anymore), is by traditional long division:

After six steps, we finally get to a remainder that was previously seen (in this case, on the first step). Therefore, we tell students, the subsequent digits have to repeat.

By the way, this is the essence of the proof for why every rational number has either a repeating decimal representation (possibly with a delay, like $0.1\overline{6}$ ) or else a terminating decimal representation. Though a more formal proof would be preferred by professional mathematicians, the idea is simple: in the algorithm for long division for $k/n$ , there are only $n$ possible remainders: $0, 1, \dots, n-1$ . So we eventually have to arrive at a remainder that was seen before. If that remainder is $0$ , then the decimal representation terminates. Otherwise, the decimal representation repeats itself.

In my experience, every math major that I’ve ever met intuitively knows that the above theorem is true. After all, they’ve worked intensively with decimals since 5th grade and have seen decimals in the lower elementary grades. However, very few can articulate why it’s true.

Thoughts on 1/7 and other rational numbers (Part 1)

I’m guessing that not many people ever blocked time out of their busy schedules to purposefully memorize the decimal representation of a fraction. Nevertheless, in my experience, most math majors and math teachers can immediately convert, from memory, most (but not all — more on this later) fractions of the form $\displaystyle \frac{k}{n}$ into its decimal representation as long as the denominator $n$ is less than or equal to $10$ . They can also go the other direction, mentally recognizing a decimal expansion as a fraction of this form.

This memorization occurs not because of purposeful study but because these fractions arise so commonly from 6th grade through college that students can’t help but memorize them. They just come up so often that good students almost can’t help but memorize them.

Here are the decimal representations of $\displaystyle \frac{k}{n}$ , where the fraction is in lowest terms and $1 \le k < n \le 10$ .

$\displaystyle \frac{1}{2} = 0.5$

$\displaystyle \frac{1}{3} = 0.\overline{3} \quad \displaystyle \frac{2}{3} = 0.\overline{6}$

$\displaystyle \frac{1}{4} = 0.25 \quad \displaystyle \frac{3}{4} = 0.75$

$\displaystyle \frac{1}{5} = 0.2 \quad \displaystyle \frac{2}{5} = 0.4 \quad \displaystyle \frac{3}{5} = 0.6 \quad \displaystyle \frac{4}{5} = 0.8$

$\displaystyle \frac{1}{6} = 0.1\overline{6} \quad \displaystyle \frac{5}{6} = 0.8\overline{3}$

$\displaystyle \frac{1}{7} = 0.\overline{142857} \quad \displaystyle \frac{2}{7} = 0.\overline{285714} \quad \displaystyle \frac{3}{7} = 0.\overline{428571}$

$\displaystyle \frac{4}{7} = 0.\overline{571428} \quad \displaystyle \frac{5}{7} = 0.\overline{714285} \quad \displaystyle \frac{6}{7} = 0.\overline{857142}$

$\displaystyle \frac{1}{8} = 0.125 \quad \displaystyle \frac{3}{8} = 0.375 \quad \displaystyle \frac{5}{8} = 0.625 \quad \displaystyle \frac{7}{8} = 0.875$

$\displaystyle \frac{1}{9} = 0.\overline{1} \quad \displaystyle \frac{2}{9} = 0.\overline{2} \quad \displaystyle \frac{4}{9} = 0.\overline{4} \quad \displaystyle \frac{5}{9} = 0.\overline{5} \quad \displaystyle \frac{7}{9} = 0.\overline{7} \quad \displaystyle \frac{8}{9} = 0.\overline{8}$

$\displaystyle \frac{1}{10} = 0.1 \quad \displaystyle \frac{3}{10} = 0.3 \quad \displaystyle \frac{7}{10} = 0.7 \quad \displaystyle \frac{9}{10} = 0.9$

Like I said, most (but not all) of these have been memorized by math majors and math teachers. The exceptions, not surprisingly, are the fractions with a denominator of $7$ .

When I was a child, I read somewhere the following rule for memorizing the decimal expansion of $\displaystyle \frac{k}{7}$ . I must have been lucky, because I have yet to meet a student that also saw this rule. The following is not a formal proof of the rule, but it does work for the purposes of memorization.

Step 1. Let’s begin with $\displaystyle \frac{1}{7}$ . The decimal expansion can be remembered by repeating “3, 2, 6” along with repeating “up, down.” Repeating both patterns, we get

up 3

down 2

up 6

down 3

up 2

down 6

So,

Start at $1$ :

up 3: $\quad 1 + 3 = 4$

down 2: $\quad 4 - 2 = 2$

up 6: $\quad 2 + 6 = 8$

down 3: $\quad 8 - 3 = 5$

up 2: $\quad 5 + 2 = 7$

down 6: $\quad 7 - 6 = 1$

The pattern returns back to $1$ , and the digits repeat. That’s the decimal expansion:

$\displaystyle \frac{1}{7} = 0.142857142857\dots$

Steps 2-6. For $\displaystyle \frac{2}{7}, \dots, \frac{6}{7}$ , the digits repeat in the same pattern as $\displaystyle \frac{1}{7}$ , just starting at a different place. For example:

For $\displaystyle \frac{2}{7}$ , the second smallest of the digits $1, 4, 2, 8, 5, \hbox{~and~} 7$ is $2$ . So we’ll drop the first $1$ and $4$ and start on $2$ :

$\displaystyle \frac{1}{7} = 0.2857142857\dots = 0.\overline{285714}$

For $\displaystyle \frac{4}{7}$ , the fourth smallest of the digits $1, 4, 2, 8, 5, \hbox{~and~} 7$ is $5$ . So we’ll drop the first $1$ , $4$ , $2$ , and $8$ and start on $5$ :

$\displaystyle \frac{4}{7} = 0.57142857\dots = 0.\overline{571428}$

P.S. Plenty of math majors (though perhaps not a majority) have also memorized the decimal expansions of $\displaystyle\frac{k}{11}$ and $\displaystyle \frac{k}{12}$ . For $11$ , the rule is multiply $k$ by $9$ to form the two-digit repeating block. In other words:

$4 \times 9 = 36$ , and so $\displaystyle \frac{4}{11} = 0.\overline{36}$

$8 \times 9 = 72$ , and so $\displaystyle \frac{8}{11} = 0.\overline{72}$

$1 \times 9 = 9$ , and so $\displaystyle \frac{1}{11} = 0.\overline{09}$

For $12$ , the only lowest-term fractions are $\displaystyle \frac{1}{12}$ , $\displaystyle \frac{5}{12}$ , $\displaystyle \frac{7}{12}$ , and $\displaystyle \frac{11}{12}$ . To begin, the first should be memorized:

$\displaystyle \frac{1}{12} = 0.08333\dots = 0.08\overline{3}$

The others are obtained by addition or subtraction:

$\displaystyle \frac{7}{12} = \displaystyle \frac{1}{2} + \frac{1}{12} = 0.5 + 0.08333\dots = 0.58333\dots = 0.58\overline{3}$

$\displaystyle \frac{5}{12} = \displaystyle \frac{1}{2} - \frac{1}{12} = 0.5 - 0.08333\dots = 0.41666\dots = 0.41\overline{3}$

$\displaystyle \frac{11}{12} = 1 - \frac{1}{12} = 1 - 0.08333\dots = 0.91666\dots = 0.91\overline{6}$

Calculator errors: When close isn’t close enough (Part 2)

In the previous post, I gave a simple classroom demonstration to illustrate that some calculators only approximate an infinite decimal expansion with a terminating decimal expansion, and hence truncation errors can propagate. This example addresses the common student question, “What’s the big deal if I round off to a few decimal places?”

(For what it’s worth, I’m aware that some current high-end calculators are miniature computer algebra systems and can formally handle an answer of $\displaystyle \frac{1}{3}$ instead of its decimal expansion.)

Students may complain that the above exercise is artificial and unlikely to occur in real life. I would suggest following up with a real-world, non-artificial, and tragic example of an accident that happened in large part due to truncation error. This incident occurred during the first Gulf War in 1991 (perhaps ancient history to today’s students). I’m going to quote directly from the website http://www.ima.umn.edu/~arnold/disasters/patriot.html, published by Dr. Douglas Arnold at the University of Minnesota. Perhaps students don’t need to master the details of this explanation (a binary expansion as opposed to a decimal expansion might be a little abstract), but I think that this example illustrates truncation error vividly.

On February 25, 1991, during the Gulf War, an American Patriot Missile battery in Dharan, Saudi Arabia, failed to track and intercept an incoming Iraqi Scud missile. The Scud struck an American Army barracks, killing 28 soldiers and injuring around 100 other people. A report of the General Accounting office, GAO/IMTEC-92-26, entitled Patriot Missile Defense: Software Problem Led to System Failure at Dhahran, Saudi Arabia reported on the cause of the failure.

It turns out that the cause was an inaccurate calculation of the time since boot due to computer arithmetic errors. Specifically, the time in tenths of second as measured by the system’s internal clock was multiplied by $1/10$ to produce the time in seconds. This calculation was performed using a 24 bit fixed point register. In particular, the value $1/10$ , which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error.

Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about $0.34$ seconds.

The number $1/10$ equals

$\displaystyle \frac{1}{2^4} + \frac{1}{2^5} +\frac{1}{2^8} + \frac{1}{2^9} + \frac{1}{2^{12}} + \frac{1}{2^{13}} + \dots$

In other words, the binary expansion of $1/10$ is

$0.0001100110011001100110011001100....$

Now the 24 bit register in the Patriot stored instead

$0.00011001100110011001100$

introducing an error of

$0.0000000000000000000000011001100...$ binary,

or about $0.000000095$ decimal. Multiplying by the number of tenths of a second in $100$ hours gives

$0.000000095 \times 100 \times 60 \times 60 \times 10=0.34$ .

A Scud travels at about $1,676$ meters per second, and so travels more than half a kilometer in this time. This was far enough that the incoming Scud was outside the “range gate” that the Patriot tracked.

Ironically, the fact that the bad time calculation had been improved in some parts of the code, but not all, contributed to the problem, since it meant that the inaccuracies did not cancel.

The following paragraph is excerpted from the GAO report.

The range gate’s prediction of where the Scud will next appear is a function of the Scud’s known velocity and the time of the last radar detection. Velocity is a real number that can be expressed as a whole number and a decimal (e.g., 3750.2563…miles per hour). Time is kept continuously by the system’s internal clock in tenths of seconds but is expressed as an integer or whole number (e.g., 32, 33, 34…). The longer the system has been running, the larger the number representing time. To predict where the Scud will next appear, both time and velocity must be expressed as real numbers. Because of the way the Patriot computer performs its calculations and the fact that its registers are only 24 bits long, the conversion of time from an integer to a real number cannot be any more precise than 24 bits. This conversion results in a loss of precision causing a less accurate time calculation. The effect of this inaccuracy on the range gate’s calculation is directly proportional to the target’s velocity and the length of the the system has been running. Consequently, performing the conversion after the Patriot has been running continuously for extended periods causes the range gate to shift away from the center of the target, making it less likely that the target, in this case a Scud, will be successfully intercepted.

A quick note of clarification. To verify the binary expansion of $1/10$ , we use the formula for an infinite geometric series.

$S = \displaystyle \left(\frac{1}{2^4} + \frac{1}{2^5}\right) +\left(\frac{1}{2^8} + \frac{1}{2^9}\right) + \left(\frac{1}{2^{12}} + \frac{1}{2^{13}}\right) + \dots$

$S = \displaystyle \frac{3}{2^5} + \frac{3}{2^9} + \frac{3}{2^{13}} + \dots$

$S = \displaystyle \frac{\displaystyle \frac{3}{2^5}}{\quad \displaystyle 1 - \frac{1}{2^4} \quad}$

$S = \displaystyle \frac{\displaystyle \frac{3}{32}}{\quad \displaystyle \frac{15}{16} \quad}$

$S = \displaystyle \frac{3}{32} \times \frac{16}{15}$

$S = \displaystyle \frac{1}{10}$

OK, that verifies the answer. Still, a curious student may wonder how one earth one could directly convert $1/10$ into binary without knowing the above series ahead of time. I will address this question in a future post.

Calculator errors: When close isn’t close enough (Part 1)

Far too often, students settle for a numerical approximation of a solution that can be found exactly. To give an extreme example, I have met quite intelligent college students who were convinced that $\displaystyle \frac{1}{3}$ was literally equal to $0.3$ .

That’s an extreme example of something that nearly all students do — round off a complicated answer to a fixed number of decimal places. In trigonometry, many students will compute $\sin \left( \cos^{-1} 0.3 \right)$ by plugging into a calculator and reporting the first three to six decimal places, like $0.95394$ . This is especially disappointing when there are accessible techniques for getting the exact answer (in this case, $\displaystyle \frac{\sqrt{91}}{10}$ ) without using a calculator at all.

Unfortunately, even maintaining eight, nine, or ten decimal places of accuracy may not be good enough, as errors tend to propagate as a calculation continues. I’m sure every math teacher has an example where the correct answer was exactly $\displaystyle\frac{3}{2}$ but students returned an answer of $1.4927$ or $1.5031$ because of roundoff errors.

Students may ask, “What’s the big deal if I round off to five decimal places?” Here’s a simple example — which can be quickly demonstrated in a classroom — of how such truncation errors can propagate. I’m going to generate a recursive sequence. I will start with $\displaystyle \frac{1}{3}$ . Then I will alternate multiplying by $1000$ and then subtracting $333$ . More mathematically,

$a_1 = \displaystyle \frac{1}{3}$

$a_{2n} = 1000 a_{2n-1}$

$a_{2n+1} = a_{2n} - 333$ if $n > 0$

Here’s what happens exactly:

$1000 \times \displaystyle \frac{1}{3} = \displaystyle \frac{1000}{3} = \displaystyle 333\frac{1}{3} = 333.\overline{3}$

$\displaystyle 333\frac{1}{3} - 333 = \displaystyle \frac{1}{3} = 0.\overline{3}$

So, repeating these two steps, the sequence alternates between $\displaystyle \frac{1}{3}$ and $\displaystyle 333\frac{1}{3}$ .

But looks what happens if I calculate the first twelve terms of this sequence on a calculator.

Notice that by the time I reach $a_{11}$ , the terms of the sequence are negative, which is clearly incorrect.

So what happened?

This is a natural by-product of the finite storage of a calculator. The calculator doesn’t store infinitely many digits of $\displaystyle \frac{1}{3}$ in memory because a calculator doesn’t possess an infinite amount of memory. Instead, what gets stored is something like the terminating decimal $0.33333333333333$ , with about fourteen $3$ s. (Of course, only the first ten digits are actually displayed.)

So multiplying by $1000$ and then subtracting $333$ produces a new and different terminating decimal with three less $3$ s. Do this enough times, and you end up with negative numbers.

Square roots and logarithms without a calculator (Part 2)

I’m in the middle of a series of posts concerning the elementary operation of computing a square root. This is such an elementary operation because nearly every calculator has a $\sqrt{~~}$ button, and so students today are accustomed to quickly getting an answer without giving much thought to (1) what the answer means or (2) what magic the calculator uses to find square roots.

I like to show my future secondary teachers a brief history on this topic… partially to deepen their knowledge about what they likely think is a simple concept, but also to give them a little appreciation for their elders. Indeed, when I show this method to today’s college students, they are absolutely mystified that a square root can be extracted by hand, without the aid of a calculator.

To begin, let’s again go back to a time before the advent of pocket calculators… say, ancient Rome. (I personally love using Back to the Future for the pedagogical purpose of simulating time travel, but I already used that in the previous post.)

How did previous generations figure out $\sqrt{4213}$ without a calculator? In the previous post, I introduced a trapping method that directly used the definition of $\sqrt{~~}$ for obtaining one digit at a time. Here’s a second trapping method that’s significantly more efficient. As we’ll see, this second method works because of base-10 arithmetic and a very clever use of Algebra I. My understanding is that this procedure was a standard topic in the mathematical training of children as little as 50 years ago.

Personally, I was taught this method when I was maybe 10 or 11 years old by my math teacher; I don’t doubt that she had to learn to extract square roots by hand when she was a student. Of course, this trapping method fell out of pedagogical favor with the advent of cheap pocket calculators.

I’ll illustrate this method again with $\sqrt{4213}$ . After illustrating the method, I’ll discuss how it works using Algebra I.

1. To begin, we start from the decimal point and group digits in block of two. (If the number had been $413$ , then the $4$ would have been in a group by itself.) I start with the $42$ . What perfect square is closest to $42$ without going over? Clearly, the answer is $6$ . So, mimicking the algorithm for long division:

We’ll place a $6$ over the $42$ , signifying that the answer is in the $60$ s.
We’ll subtract $36$ from $42$ , for an answer of $6$ .

2. On the next step, we’ll do a couple of things that are different from ordinary long division:

We’ll bring down the next two digits. So we’ll work with $613$ .
We’ll double the number currently on top and place the result to the side. In our case $6 \times 2 = 12$.
We’ll place a small ___ after the $12$ and under the $12$ .
The basic question is: I need $120$ –something times the same something to be as close to $613$ as possible without going over. I like calling this The Price Is Right problem, since so many games on that game show involve guessing a price without going over the actual price. For example…

$121 \times 1 = 121$ : too small

$122 \times 2 = 244$ : too small

$123 \times 3 = 369$ : too small

$124 \times 4 = 496$ : too small

$125 \times 5 = 625$ : too big

Based on the above work, the next digit is $4$ . We place the $4$ over the next block of digits and subtract $124 \times 4 = 496$ from $613$ . So we will work with $613-496 = 117$ on the next step.

3. On the next step, we’ll do a couple of things that are different from ordinary long division:

We’ll bring down the next two digits. On this step, the next two digits are the first two zeroes after the decimal point. So we’ll work with $11,700$ .
We’ll double the number currently on top and place the result to the side. In our case $64 \times 2 = 128$.
We’ll place a small ___ after the $128$ and under the $128$ .
The basic question is: I need $1280$ –something times the same something to be as close to $11,700$ as possible without going over. For example…

$1281 \times 1 = 1281$ : too small

$1282 \times 2 = 2564$ : too small

$1283 \times 3 = 3849$ : too small

$1284 \times 4 = 5136$ : too small

$1285 \times 5 = 6425$ : too small

$1286 \times 6 = 7716$ : too small

$1287 \times 7 = 9009$ : too small

$1288 \times 8 = 10,304$ : too small

$1289 \times 9 = 11,601$ : still too small

Based on the above work, the next digit is $9$ . We place the $9$ over the next block of digits and subtract $1289 \times 9 = 11,601$ from $11,700$ . So we will work with $11,700-11,601 = 99$ on the next step.

Then, to quote The King and I, et cetera, et cetera, et cetera. Each step extracts an extra digit of the square root. With a little practice, one gets better at guessing the correct value of $x$ .

A personal story: when I was a teenager and too cheap to buy a magazine, I would extract square roots to kill time while waiting in the airport for a flight to start boarding. My parents hated missing flights, so I was always at the gate with plenty of time to spare… and I could extract about 20 digits of $\sqrt{2}$ while waiting for the boarding announcement.

So why does this algorithm work? I offer a thought bubble if you’d like to think about before I give the answer.

P.S. In case anyone complains, the people of ancient Rome could not have performed this algorithm since they used Roman numerals and not a base 10 decimal system.

To see why this works, let’s consider the first two steps of finding $\sqrt{4213}$ . Clearly, the answer lies between $60$ and $70$ somewhere (that was Step 1). So the basic problem is to solve for $x$ if

$(60+x)^2 = 4213$ ,

where $x$ is the excess amount over $60$ . Squaring, we obtain

$3600 + 120x + x^2 = 4213$ ,

$120x + x^2 = 613$ ,

$(120+x)x = 613$

Notice that the right-hand side is $4213-3600$ , which was obtained at the start of Step 2. The left-hand side has the form $120$ –something times the same something, which was the key part of completing Step 2. So the value of $x$ that gets $(120+x)x$ as close to $613$ as possible (without going over) will be the next digit in the decimal representation of $\sqrt{4213}$ .

The logic for the remaining digits is similar.

I should mention that third roots, fourth roots, etc. can (in principle) be found using algebra to find excess amounts. However, it’s quite a bit more work for these higher roots. For example, to find the cube root of $4213$ , we immediately see that $10^3 = 1000 < 4213 < 8000 = 20^3$ , so that the answer lies between $10$ and $20$ . To find the excess amount over 10, we need to solve

$(10+x)^3 = 4213$ ,

which reduces to

$(300 + 30x + x^2)x = 3213$ .

So we then try out values of $x$ so that the left-hand side gets as close to $3213$ as possible without going over.

In closing, in honor of this method, here’s a great compilation of clips from The Price Is Right when the contestant guessed a price that was quite close to the actual price without going over.