Challenge #12 solution, part I

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

To recap, the question in question went as follows:

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?

Before I give the solution, let me ask a slightly different question instead: given a positive integer n, in how many ways can n be written as a sum of powers of ten, when each power is allowed to occur at most nine times?

Well, let’s see… we’ll try an example. Let’s try writing 436 as a sum of powers of ten, with at most nine copies of each power. Well, notice that since all powers of ten from $10^1$ and up are divisible by ten, the only way to get the ‘6’ at the end of 436 is to use six copies of $10^0 = 1$ , leaving us with 430. Now, about that 30… we can only use $10^1$ or $10^0$ , since any higher powers of ten will be divisible by 100. But we can’t use $10^0$ since we don’t have enough of them to add up to 30. So we’ll have to use three copies of $10^1$ . Finally, we have to use four copies of $10^2$ . So, all told, it seems as though there’s only one way to write 436:

$436 = 4 \times 10^2 + 3 \times 10^1 + 6 \times 10^0$ .

…waaaait a minute…! That’s exactly what the notation ‘436’ means — four hundreds, three tens, and six ones! And the answer to the question is, of course, that there is exactly one way to write any number n as a sum of powers of ten when at most nine copies of each power are allowed — and this is why our base-ten system of writing numbers works! We take it completely for granted, but it’s actually fairly remarkable that such a simple system for uniquely representing integers exists. And as natural as it seems to us, it isn’t obvious — it was invented by Indian mathematicians as early as 500 AD, but didn’t really catch on in Europe until about a thousand years later!

So, going back to the original question, it turns out that there is exactly one way to write any given positive integer as a sum of powers of two, with each power occurring at most once; this system of uniquely representing positive integers is called base two, or binary. As you may know, this is the system that computers use to represent data. Every single piece of data stored by a computer — videos, images, software, text, this blog post itself — is ultimately encoded as a series of numbers, which are in turn encoded in binary.

How can we prove this? Let $b(n)$ denote the number of ways to write the positive integer n as a sum of powers of two with each power occurring at most once. Clearly $b(1) = 1$ (there’s only one way to write $1 = 2^0$ ). Now suppose we have some positive integer n which is even, so we can write $n = 2k$ for some integer k. Any way of expressing n as a sum of powers of two cannot include $2^0 = 1$ , since any sum that includes $2^0$ exactly once must be odd (all the other powers of two are even, and even + even = even, even + odd = odd). (Of course, a sum which includes $2^0$ twice could be even — but we are only allowed one copy of each power.) Therefore, given powers of two summing to n, we can just divide each of them by two (so e.g. $2^5$ becomes $2^4$ , and so on) to get a list of powers of two which add up to $n/2 = k$ . Conversely, any powers of two summing to k can all be multiplied by two to give powers of two summing to n. Since each way of writing n corresponds to a way of writing k and vice versa, the number of ways of writing them must be the same: $b(2k) = b(k)$ .

Now suppose $n = 2k + 1$ is odd. Any list of powers of two summing to an odd number must include $2^0 = 1$ . If we remove the $2^0$ , we are left with ways of summing to $n - 1 = 2k$ . And vice versa, any way of summing to $2k$ can be made into a way of summing to $2k + 1$ by just adding $2^0$ . So $b(2k+1) = b(2k)$ .

But since $b(1) = 1$ , and $b(n)$ is always equal to the value of b for some smaller number, it is not hard to see that $b(n) = 1$ for all n. For example, $b(7) = b(6) = b(3) = b(2) = b(1) = 1$ .

All in all, this is a rather roundabout way to show that there is only one way to write each number as a sum of powers of two with at most one copy of each power! There are probably easier ways to demonstrate this. However, a generalization to the above approach can be used profitably to attack the other two problems, so you can additionally consider this post as a hint. =)

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

8 Responses to Challenge #12 solution, part I

Steve Gilberg says:

April 22, 2008 at 8:52 am

…Didn’t catch on until about 1500 AD? What did they do in the interim? I suppose they used Roman numerals, but what names did they have, say, in Chaucer’s England for numbers, I wonder?
Brent says:

April 22, 2008 at 9:41 am

Yup, I’m pretty sure they used Roman numerals. But I don’t know how they pronounced the numbers, that’s a really good question! I’d guess that they actually used something very close to the number-names that we still use today — the Roman numeral system is still strongly related to powers of ten. But maybe for 367 they said something like “three hundreds, fifty, and seventeen”. This is complete and utter speculation on my part. Maybe I will ask my friend who studies medieval literature.
Jason Dyer says:

April 22, 2008 at 8:22 pm

Well, if you want to see what Chaucer himself wrote, try his Treatise on the Astrolabe.

A line from Canterbury Tales has the first known example of the word “degree”; it also appears in this work.

From page 34 of the edition I linked to:

The yere of oure Lorde a thousand thre hundred ninetie and one, the twelveth daie of March, I would knowe the tide of the daie. I toke the altitude of my sonnne and founde that it was XXV degrees and XXX minutes of height of the bordure in the bakksyde: tho tourned I myne astrolabie, and bicause it was before middaie I tourned my rete and sette the degre of the sonne, that is to saie the firste degre of Aries, in the righte side in myne astrolabie, upon the XXV degre and XXX minutys of height emong my almicanteras.
Steve Gilberg says:

April 25, 2008 at 9:09 am

If Chaucer said “ninetie,” then they must have had a base-10 system by that time.
Jason Dyer says:

April 25, 2008 at 12:04 pm

The Romans also used base 10. Take a look at their Latin words for numbers.

It’s not like base 10 wasn’t understood; it was only the *notation* that “1391” is equivalent to “one thousand three hundred ninety and one” wasn’t used yet. (Reading over the original blog entry, I do see how there is a bit of confusion over this; mathmatically, the ancients were already there as far as understanding base systems. The big missing piece of the puzzle was zero-as-placeholder, which the Babylonians hit at one point [still not getting zero as a solitary number] and from my recollection this convention pops in and out of history at that point until it becomes standard.)
Brent says:

April 25, 2008 at 12:33 pm

Yeah, after studying this some more and talking to a friend who studies medieval literature, I realized that Jason is exactly right: I had initially conflated the ideas of having a base ten system of numbers, and having a positional notation for writing numbers, where the same symbol can be used to represent different quantities depending on its position (e.g. the ‘3’ in ’43’ means ‘three’ but in ’35’ it means ‘thirty’). The former has been around for a long time (it’s quite natural given various obvious anatomical facts), but the latter is relatively much more recent.
Jonathan says:

June 19, 2008 at 9:21 pm

“Base 10 works because it uniquely represents numbers” was enough to blow my mind.
Pingback: Math Teachers at Play #21 « The Math Less Traveled

Comments are closed.