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:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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:

i-88516ca505d84f969b7ab15a965c3fb3-2.png

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:

i-d18063683dcc0d42b9be45451a84d1e3-3.png

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:

i-8d7070ce28f0af28047c7a5fb8246d53-4.png

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?]

More like this

This isn't very elegant, but it saves time by not calculating values of b higher than n. (You said, however, to only return all values below n.)

n = 2^10;
Sort@DeleteDuplicates@Flatten@Table[2^i 5^j, {i, 0, Log[2, n]}, {j, 0, Log[5, 2^-i n]}]

By Andrew Belt (not verified) on 23 Jan 2011 #permalink

Technical point: the rationals include zero and the negatives. The a and b in a/b need only be integers, with b nonzero.
Pickiness aside, I thoroughly enjoy your blog! Please keep up the good work :-)

Every terminating fraction also has a repeating representation that ends in all 9s:

0.25 = 0.24999999...

...

The observation about when a fraction's representation terminates extends in the obvious way to different number bases. (That is, the repesentation terminates if and only if denominator shares all of its prime factors with the base.)

...

You mention that Ï is irrational and then say "This isn't too difficult to prove."

I am curious to know what your "not too difficult" proof looks like. :-)

I should say "Not too difficult for a mathematician". ;) In any case, the proof is a lot easier than the proof that pi is transcendental! A better example of an honestly easy irrationality proof is the square root of 2, which is all over the internet and probably illustrates the point better.

The question of decimal representations ending in repeating 9s is a fun one, crucial to the perennial internet arguments that crop up over the 1 = 0.999... question. I believe Hardy sets up his definitions such that the representation with repeating 9s isn't possible in the first place. It's my understanding that this unique representation is a little nonstandard, with the reals usually defined such that (for instance) 0.4999... = 0.5

A question about bases. Is it possible/sensible to talk about baseÏ?; Would Ï in baseÏ be 1?, what would happen to eiÏ ?

@Ross: No. It only makes sense to use positive integers for bases (and even then, base 1 is tricky).

By Eric Lund (not verified) on 24 Jan 2011 #permalink

A proof of the irrationality of pi eluded the ancient Greek
matematicians including Archimedes despite his extensive study of pi.

Hermite's proof is at least short but since nobody had noticed it before it probably shouldn't be described as
easy.

How difficult a proof is is somewhat subjective. It's not
clear to me that the Lambert-Legendre proof of the irrationality of pi is less difficult than the Lindemann-
Weierstrass proof that pi is transcendental.

By Annonymous (not verified) on 24 Jan 2011 #permalink

In contrast to pi the proof that e is irrational really is
easy. At least it is easy if you start with the factorial
series for e.

By Annonymous (not verified) on 24 Jan 2011 #permalink

DeleteDuplicates? Apparently you don't believe in unique factorization.

Base pi might not make a lot of sense, but bases don't have to be integers. Look at how the pages of the xkcd book 0 are numbered. Well, that's really not a number base precisely, more a system of representation that is sort of like a base. OK, then, how about base 3/2, like Jim Tanton taught me? If you use the digits 0, 1, and 2 and the place value of powers of 3/2 then you get some pretty interesting stuff.

Not familiar with mathematica, but at a guess:

Flatten[Table[2^i 5^j, {i, 0, floor(log(n)/log(2)) }, {j, 0, floor(log(n)/log(5))}]]]]

You don't need delete duplicates: all the numbers are unique.

Try limiting your second loop. In a more psudeocode form:

for i = 0 to floor(log(n)/log(2))
for j = 0 to floor( log(n / 2^i) / log 5 )
print 2^i 5^j

This won't sort, but it will almost do what you want.

To get the numbers sorted, answer this question: I have log(b) = i*log(2) + j*log(5). What {i,j} tuple will give me the next largest log(b)? Perhaps divide through by log(2) to make it clearer?

By Paul Murray (not verified) on 25 Jan 2011 #permalink