Sunday Function

In my free time during data acquisition runs and the like, I've been paging through Hardy and Wright's famous textbook An Introduction to the Theory of Numbers. It has something of a legendary reputation among pure math textbooks, and so far as I can tell it is entirely deserved.

One of the topics treated in the book is the representation of numbers in the decimal system. In some ways it's an elementary topic, but it also serves as a starting point for some genuinely deep mathematics. Today I'd like to noodle around with the connection between fractions and decimals. It's a bit of a stretch to tack the word "function" onto any of this, but we'll let this discussion slide because we can always write a fraction as the output of a function f with two arguments: f(a,b) = a/b.

Ok. When I say "fraction", I have in mind the more solid idea of a rational number in mind. A rational number is a number of the form a/b, where a and b are both natural numbers. Natural numbers are the positive whole numbers 1, 2, 3... and so forth.

Not every number is a rational number. As an example, π = 3.14159... is not a rational number because it can't be written in the form a/b where a and b are both natural numbers. This isn't too difficult to prove. For purposes of approximation there are rational numbers that are close to π. 22/7 = 3.14286... is not far off, for instance. But close to π is not equal to &pi, and thus it and many other numbers like e and the square root of 2 simply can't be written exactly as a rational fraction.

In both cases I've put an ellipsis to indicate the fact that there are more decimal digits to the right. This does obscure an important difference between the rational and irrational numbers. The decimal expansion of rational numbers always repeats or terminates. For instance, 1/4 = 0.25 which terminates by virtue of having a finite decimal expansion. 1/3 doesn't terminate, but it does repeat: 1/3 = 0.3333.... (Alternately you could write 1/4 = 0.25000000... and say that the decimal expansion of every rational number repeats, some with an infinite string of 0s. Call that latter possibility "terminating" and the discussion doesn't change.) But irrational numbers never fall into an eternally repeating pattern. Though they may have instances of including some string of digits several times in a row, an irrational number will never start repeating forever.

The proof that a non-repeating decimal is equivalent to not being expressible as a rational a/b only takes up about one pretty easy page in Hardy and Wright, but it requires more background from earlier in the book than we can comfortably accommodate here. Instead, let's take a look at what makes the difference between rationals that terminate and rationals that don't.

We know that multiplying a number by 10 essentially just moves the decimal point over one step to the right. Multiplying it by 100 moves it over two steps, and multiplying by 10^n moves it over n steps. Therefore if a decimal expansion terminates after n decimal digits, we can turn it into a good old fashioned natural number by multiplying it by 10^n. For instance, if our decimal number is 0.014, we can say:

We can clearly repeat this kind of procedure on any terminating decimal, turning it into a natural number. Therefore if a particular rational number a/b is represented by a terminating decimal, we can do the same kind of procedure on it: multiply by 10^n and turn it into a natural number N:

What a/b will this work on? Right away we see that if b is of the form b = 10^n, we're set and the decimal terminates. For instance, 9/100 = 0.09, which terminates. But clearly that's not the only terminating form, because some natural numbers like 1/4 and 1/5 terminate as well despite not being of that form. To fix this, remember that 10 can be factored - written as the product of primes. 10=5*2. This means that our criterion can also be written as:

The 2s and 5s can cancel out any b that happens to be the product of 2s and 5s. For instance, the rational number 1/5 has b = 5, so multiplying (2*5)*(1/5) will result in the denominator being canceled. You've got an extra factor of 2 left over in the numerator, but who cares? All that needs to happen is that we end up with a natural number, which as we demonstrated automatically means the decimal expansion will terminate.

And that's it. A fraction a/b will have a terminating decimal expansion if and only if:

for natural numbers α and β. The first few b's that work are 1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, and 128. Fractions with one of those in the denominator will terminate, for instance, 19/64 = 0.296875 exactly.

Even grade school math has its interesting features, and I'll have to admit I had never really thought about what distinguished the terminating decimal representations from those that did not. But now I know.

[Technical question/quiz for the Mathematica wizards out there - to generate the list of b's, I used Sort[DeleteDuplicates[
Flatten[Table[2^i 5^j, {i, 0, 10}, {j, 0, 5}]]]]. This was fine for quickly generating the b's I wanted, but not for generating all the working b's in order with no gaps after 2^10. What's a cleaner, Mathematica-lly elegant way to get all the b's below some value?]