The Math Less Traveled

Quan, Daniel, and Sol, from blinkdagger and Wild About Math!, have teamed up to create a fun math contest, Monday Math Madness. Every other week, they post a math problem; after one week, a winner is randomly selected from among those sending in a correct answer, and receives a real honest-to-goodness prize!

The current contest was just posted today. Go give it a try, and send in your solution — maybe you’ll win! Even if you don’t, of course, it’s still a fun problem. Here it is:

Aside from 1 and 9, are there any perfect squares whose digits are all odd? Justify your answer.

Don’t post any answers or discussion here! If you think you’ve solved it, send your answer to mondaymathmadness at gmail dot com.

And now for the solution to problem #3 from Challenge #12, which asked: how many ways are there to write a positive integer n as a sum of powers of two, with no restrictions on how many powers of two may be used?

Read the rest of this entry »

I’ll begin by providing an answer to the first of the three questions I posed in a previous post.

Read the rest of this entry »

A few interesting problems for you to think about:

1. Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most once? For example, 11 can be written as . But we’re not allowed to write , since occurs twice. The order of the terms in the sums don’t matter, so and don’t count as different sums.
2. Now what if we allow at most two copies of each power of two? Both of the examples for 11 shown above would be allowed now. Say denotes the number of different ways to write n as a sum of powers of two with at most two copies of each power allowed. What can you say about the function h?
3. What if we allow an unlimited number of each power of two? Now how many ways are there to write n as such a sum?

Post your solutions in the comments (partial solutions are welcome and encouraged), but only if you didn’t know the answer as soon as you read the question. =)

Hello again, dear reader!

I haven’t written anything here in quite a while now — since February 22, it would seem! Partly, that’s because I’ve been busy visiting graduate schools and deciding where to go. And I can now happily announce that my wife and I will be moving to Philadelphia this summer, where I will begin a computer science PhD at the University of Pennsylvania in the fall. I’m super excited!

So, what does that mean for this blog? Not to worry — as of right now, I plan to continue right on with the same tasty accessible math you’ve come to (hopefully) love and (rightfully) expect! Plans can always change, of course, but right now I intend and hope to continue this blog while in grad school. Will I keep writing this blog until I die? Probably not! I’ll stop at some point, but that point isn’t here yet. =)

For now, a link: if you haven’t yet read “A Mathematician’s Lament” by Paul Lockhart — a telling and insightful lament over the current state of mathematics education in the US, which transcends the usual petty debates — I highly recommend it, whether you’re a teacher, a student, or (ideally) both! It’s both depressing and inspiring at the same time. He puts eloquent and forceful words on things I’ve thought only dimly.

#1000, you ask? Surely the previous one was #26?

Well, yes, but that’s 1000 in base 3, of course. Duh. =)

Anyway, yes, the most recent Carnival can be found over at JD2718. Some of my favorite posts:

• A really neat, elegant correspondence between rational numbers and Pythagorean triples
• Math on Display — beautiful mathematical pictures!
• A fun geometry puzzle that seems a lot harder than it really is =)
• A nice article (with more pretty pictures) on visual methods in mathematics

Lots of other great stuff there too, go take a look!

Suppose we have two integers, and we’d like to find their greatest common divisor (GCD). Recall that the greatest common divisor of two integers m and n is exactly that: the greatest integer which is a divisor of both m and n. The obvious way to do this—which is probably the way you learned in elementary school, when reducing fractions—is to factor each integer into primes, and look for overlap. For example, let’s say we want to find the GCD of 450 and 525. We begin by factoring:

Now we pull out as many prime factors as we can which are contained in the factorizations of both numbers. We can’t use 2 at all, since it is only contained in the factorization of 450; we can use a factor of 3, but only one; and we can use two factors of 5. Putting these together, the greatest common divisor of 450 and 525 is .

This method is intuitive, and works well for relatively small numbers, but (there’s always a “but”, isn’t there?) it fails horribly for larger numbers. For example, what if you wanted to find the GCD of 2257394839 and 45466644967? (Go ahead, try it! =) The problem is that factoring is hard, even for computers—where by “hard” I mean “hard to do quickly”. It’s easy to write computer programs to do factoring, it’s just that no one knows how to write a program which factors large numbers quickly. (By “large” in this context I mean numbers with hundreds of digits; the two numbers I gave as an example above could be factored very quickly by a computer, but I bet YOU can’t factor them quickly, so the point is the same.)

Well, as you probably guessed, there’s a better algorithm for calculating the GCD of two numbers, since the GCD can actually be found without any reference to factorizations. This better algorithm is called the Euclidean Algorithm, in honor of Euclid, the first mathematician to write it down (around 300 BC, making it one of the oldest algorithms known!). It’s based on the property I showed (and proved) in my last post, namely, that

.

(Technically, in my last post I showed that , but since anything that divides x also divides -x, we can flip around the m-n if we want: anything that divides m-n will also divide -(m-n) = n-m, and vice versa.) Here’s how it works:

1. Given two integers m and n, if they are the same, then clearly they are equal to their greatest common divisor.
2. Otherwise, reduce the larger of the two numbers by subtracting the smaller number from it.
3. Lather, rinse, repeat.

That’s it. Were you expecting something more complicated? We already know that doing the subtraction step doesn’t change the GCD, and since the numbers are always getting smaller, the algorithm must eventually stop. Genius! That Euclid was one smart dude. Anyway, let’s try it on a simple example: finding the GCD of 56 and 20.

1. 56 is greater than 20, so subtract 20 from 56, leaving 36 and 20.
2. 36 is still greater than 20, so subtract 20 again, leaving 16 and 20.
3. Subtract 16 from 20, leaving 4 and 16.
4. Subtract 4 from 16 three times, eventually leaving 4 and 4.
5. Hence the GCD of 56 and 20 is 4! (This is easy to verify by factoring.)

Neat! But… what has all this got to do with the Calkin-Wilf tree? Well, if you haven’t already noticed, the Euclidean algorithm is exactly the same as the method for finding your way “up” the Calkin-Wilf tree! In particular, since all the rationals in the Calkin-Wilf tree are in lowest terms, finding your way up the Calkin-Wilf tree from m/n exactly corresponds to using the Euclidean Algorithm on m and n in order to show that their GCD really is 1. And in general, if , running the Euclidean Algorithm on m and n is like finding your way up a Calkin-Wilf tree in which all the numbers have been multiplied by d (so that it starts at d/d instead of 1/1). In an important sense, we can say that the Calkin-Wilf tree is the Euclidean Algorithm, in tree form!

In closing, I should note that in practice there’s a slight improvement we can make upon the basic Euclidean Algorithm. To see what it is, consider running the Euclidean Algorithm on 20451 and 2. Well, 20451 is bigger than 2, so subtract 2 from 20451, leaving 20449 and 2. Subtract 2 again, leaving 20447 and 2. 20447 is still bigger than 2, so subtract… this is the point where we start getting very bored. Everyone can see perfectly well that since 20451 is odd, after subtracting 2 enough times, we will eventually be left with 1. So this suggests our practical improvement: at each step, instead of replacing the larger number by the remainder when subtracting the smaller number, replace it by the remainder when dividing it by the smaller number—since division can be viewed as repeated subtraction. Now, using this improved method, can you find the GCD of 2257394839 and 45466644967?

The 26th Carnival of Mathematics—the one-year anniversary edition!—is posted over at 360, so head over and give it a look! Of particular interest to readers of TMLT are Music From Mathematical Constants from Mike at Walking Randomly (pi as music? sweet!), and The secret of Egyptian Fractions from Denise at Let’s play math!. Of course, there’s also a post by yours truly! But there’s lots for everyone, so go check it out.

Continuing a series about the Calkin-Wilf tree (see those links for some background), today I’d like to show why all the rationals in the tree must be in lowest terms. Let’s start off with a little number theory!

What do we mean when we say that a fraction is “in lowest terms”? We simply mean that the numerator and denominator have no common factors other than 1. So is in lowest terms, but isn’t, since the numerator and denominator are both divisible by 7. You will sometimes also hear the term relatively prime to describe two numbers which have no common factors. It doesn’t really have anything to do with being prime; for example, 6 and 49 are relatively prime (and hence is in lowest terms), even though neither 6 nor 49 is prime.

A more formal way to talk about all of this is in terms of the greatest common divisor, or GCD. The GCD of two numbers m and n, often written , is the largest number which evenly divides both m and n. For example, , since 6 is the largest number which evenly divides both 12 and 30. So, in particular, we can say that m and n are relatively prime when .

You should be able to verify a few simple properties of the GCD function yourself. For example, , and . Another slightly less obvious property, but more important for our purposes, is that . Why is this? Well, suppose . That means d divides both m and n, so we can write and . Therefore , so d divides m+n too! So, d is a common divisor of m and m+n. Note also that if anything bigger than d was a common divisor of m and m+n, then this larger divisor would also divide , so it would be a common divisor of m and n — but we already know that d is the greatest common divisor of m and n. Therefore, d really is the greatest common divisor of m and m+n, and . The argument to show that is exactly the same.

Applying this to the Calkin-Wilf tree is a piece of cake. We want to show that for every in the Calkin-Wilf tree, it is the case that . Well, it’s certainly true for the root node, 1/1: . And supposing it is true for some node , it must also be true for the child nodes, since we know that . And we’re done! This is a nice example of a proof by induction: all we have to do is prove that something is true for some starting value, and that whenever it is true for one thing it must be true for the next, and voilà! We have proved it for an infinite series of cases.

So, we now know that the Calkin-Wilf contains every positive rational, in lowest terms, exactly once! Next time, I’ll talk about a way to compute the GCD of two numbers, called the Euclidean Algorithm—which is probably a lot different than the way you learned to compute GCDs in elementary school—and its cool connection to the Calkin-Wilf tree.

First, a quick recap: continuing an exposition of the paper Recounting the Rationals, we’re investigating the tree of fractions shown below (known as the Calkin-Wilf tree), which is constructed by placing 1/1 at the root node, and giving each node the two children (on the left) and (on the right). Here are the first four levels of the tree (of course, it has infinitely many levels):

In my last post I claimed that this tree has a number of remarkable properties; in this and subsequent posts I plan to show exactly why these properties are true, since for the most part they have relatively simple explanations—although that in no way makes them any less remarkable!

Today let’s begin by tackling the first property I claimed, namely, that every single positive rational number occurs somewhere in this tree. How can we prove this?

First, notice that given any rational in the tree, there is any easy way to tell whether it is the left or right child of its parent. (Can you figure it out before reading on?)

Since left children are always of the form , they will always have a denominator greater than their numerator (, since j is positive); and vice versa for right children, which are of the form and consequently have a numerator greater than their denominator. So, given some fraction in the tree , to decide whether it is a left or right child, just compare m and n. If n is greater, it is a left child, and its parent is ; otherwise, it is the right child of .

For example, if we start with 5/3, we see that 5 > 3, so 5/3 must be the right child of (5-3)/3 = 2/3; 2/3, in turn, has a greater denominator, so it is the left child of 2/(3-2) = 2/1, and 2/1 is the right child of 1/1.

In fact, it is easy to see that I’ve just described a simple procedure for finding your way up the tree, starting from any positive rational in lowest terms. At each step, just take the numerator and denominator, and subtract the smaller from the larger. (They can never be equal until we get to 1/1, since we start out with something in lowest terms.) But how do we know that we will eventually reach 1/1 this way? Well, both the numerator and the denominator are always positive during this process (they start out positive, and you can’t get something negative by subtracting something smaller from something larger), and one of them gets smaller at every step. Think about this for a minute. They must eventually reach 1/1 — there’s nowhere else for them to go!

Well, if we can find a path up to 1/1 from any reduced positive rational, every such rational must be in the tree in the first place! You may also note that since we have no choice at each step, there is exactly one path from any rational up to the root of the tree — which means that each reduced rational occurs in only one place in the tree; there are no duplicates.

Now, technically, one thing we haven’t shown is that there aren’t any unreduced rationals which sneakily sneak in along with the reduced ones; but that’s not too hard to show, and I’ll talk about that next time.

There are several other interesting things going on here — for example, the path from any reduced rational up to the root of the tree corresponds directly to using the Euclidean Algorithm to prove that the rational is, in fact, reduced! And if you interpret the lefts and rights in the path as zeros and ones in binary… but I’m getting ahead of myself, that’s for a later post. =)