June 2009
—————————
In my June diary I posed the following brain-teaser:
My house is on a street where the numbers 1, 2, 3, … run consecutively with no gaps. My own house number has three digits. Curiously, the sum of all the house numbers in the street less than mine is the same as the sum of all the house numbers in the street greater than mine.
What is my house number? How many houses are there on my street?
—————————
Solution
This particular zone of number theory is governed by Pell's Equation, which arises in a natural way from the fact that the square root of 2 is irrational.
It follows that no whole-number square can ever be the double of another. It can never be the case, for whole numbers M and N, that M ² = 2N ²
Well, that's kind of a shame. You often get fruitful results in math, though, by asking a question of the following type: "OK, I can't possibly get result XXXXXXX. But can I get something close to it? How close?"
In this case, we might ask: OK, I can't get a square that differs from another square's double by nothing at all. Can I get them to differ by just one, though? Can I get M ² = 2N ² ± 1 ?
To put the question in its more usual form, I want whole-number solutions of the equation x ² −2 y ² = ± 1. This is a particular example of Pell's Equation: x ² −dy ² = ± 1, d understood to be some whole number.
In the particular case d = 2, you can get the result from a simple fact about √2. Here's the fact: (√2 − 1) × (√2 + 1) = 1. You can easily confirm this for yourself by just multiplying out the parentheses.
That simple fact can be rewritten as: √2 − 1 = 1 / (1 + √2). That in turn is equivalent to:
√2 = 1 + 1 / (1 + √2)
Since the right-hand side is equal to √2, I can substitute it anywhere I see √2. I can, for example, substitute it in itself!
√2 = 1 + 1 / (1 + (1 + 1 / (1 + √2)))
Furthermore, I can keep on doing that for as long as I care to, getting an expression like this:
√2 = 1 + 1 / (2 + 1 / (2 + 1 / (2 + 1 / (2 + 1 / (2 + 1 / (2 + …))))))
That kind of thing is called a continued fraction. If you "stop" it at some point and just work out what you've got, you've got an actual fraction. For example, 1 + 1 / (2 + 1 / (2 + 1 / 2)) works out to 17/12. These fractions, as you would expect, get closer and closer to the complete, infinite, continued fraction — whose value, remember, is √2. They are called convergents to the infinite continued fraction. For the particular infinite continued fraction I'm using, the first few convergents are 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, … Their decimal values, rounded to six decimal places, are: 1.000000, 1.500000, 1.400000, 1.416667, 1.413793, 1.414286, 1.414201, … and they do indeed seem to be closing in on √2, whose decimal value is 1.414213562373…
If you make a table of the numerators and denominators in those convergents, it looks like this:
| Numerator | Denominator |
|---|---|
| 1 | 1 |
| 3 | 2 |
| 7 | 5 |
| 17 | 12 |
| 41 | 29 |
| 99 | 70 |
| 239 | 169 |
If you stare hard at that for a minute or two, you'll see that each denominator is just the sum of the two numbers in the row above: 29 = 12 + 17. Staring a minute or two longer will reveal that each numerator is the numerator from the row above added to twice the denominator in that row: 41 = 17 + 2×12. From what has gone before, this has to be so: I'll leave you to prove that.
If you stare a bit longer you'll spot another interesting thing: In each row, the square of the numerator minus twice the square of the denominator is either plus one or minus one: 7² − 2×5² = −1, but 17² − 2×12² = +1. This also has to be so, and it's not much harder to prove.
In other words, the rows of that table are whole-number solutions of x ² −2 y ² = ± 1. They are in fact the only solutions. To prove that is another degree more difficult.
What's this got to do with my house-number brainteaser? Well, if my house number is m and there are n houses on the street, then the brainteaser tells me that:
1 + 2 + … + (m − 1) = (m + 1) + (m + 2) + … + n.
There is a well-known formula for the sum of all whole numbers from 1 to k: the sum is ½ k(k + 1). For example, 1 + 2 + 3 + 4 is ½×4×5.
Applying that formula and doing some algebraic tidying-up, my brainteaser reduces to:
(2n + 1)² − 2(2m)² = 1.
So I can pluck my 2n + 1 and my 2m from the table above, so long as the other conditions of the problem are satisfied.
The very next row in fact gives the answer we want: 2n + 1 = 577, 2m = 408. So my house is 204 on a street of 288.