## 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 streetlessthan mine is the same as the sum of all the house numbers in the streetgreaterthan 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* ² = 2*N* ²

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* ² = 2*N* ² ± 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* ² −*d**y* ² = ± 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 2*n* + 1 and my 2*m* 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:
2*n* + 1 = 577,
2*m* = 408. So my house is 204 on a street of 288.