A quick one

[Zag]

A co-worker told me this morning that he was cleaning out his father's attic and came across a very old book of puzzles. He had flipped through it and there was one he particularly liked, and I had never heard it before.

I worked on it through the two meetings I had this morning, and a couple of times heard, "Well, what do you think, Zag?" and had to have the question repeated. I did get it, though

-----------------------

I live on a street on which the houses are numbered from 1 up, with none missing. I noticed recently that the sum of all the house numbers less than mine exactly equals the sum of all the house numbers greater than mine. My house number has three digits. What is it?

[Chuck]

Yes, there is a solution. But a computer search made it too easy.

[ralphmerridew]

Doing it by hand:


m == my house number
n == highest house number
Sum of numbers less than your house == m(m-1)/2
Sum of all numbers == n(n+1)/2

(Sum of all numbers less than mine) + mine + (sum of all greater than mine) = sum of all
m(m-1)/2 + m + m(m-1)/2 = n(n+1)/2
m(m-1) + 2m + m(m-1) = n(n+1)
mm-m + 2m + mm - m = nn + n
2mm = nn + n
8mm = 4nn + 4n
8mm + 1 = 4nn + 4n + 1
2(2m)^2 + 1 = (2n+1)^2
(2n+1)^2 - 2(2m)^2 = 1
Set x = (2n+1), y = 2m
xx - 2yy = 1.
This is a Fermat-Pell equation. Generator is 3 + 2sqrt(2). All solutions are of form x + ysqrt(2) = (3 + 2sqrt(2))^k.

3 + 2 sqrt 2
17 + 12 sqrt 2
577 + 408 sqrt 2

m = y/2 = 204
n = (x-1)/2 = 288

Answer is 204.

[Zag]

I knew GL would have a better way of solving it than I. Nicely done, rm.

I had said

m == my house number
n == highest house number
Using the approach that the sum from x to y is the average of x and y times the difference
Sum of numbers less than my house == m(m-1) /2
Sum of numbers greater than my house == (m+1 + n)(n-m) /2

Set these equal to each other and do some algebra

m(m-1) = (m+1 + n)(n-m) = mn + n + nn - mm - m - mn

The mn terms conveniently fall away, leaving

mm - m = nn + n - mm - m
2mm = nn + n
mm = n(n + 1) / 2

At this point I was quite surprised that it simplified so that m squared was another triangular number, but I guess, looking at rm's approach, it was kind of obvious that it would. I didn't know anything about Fermat-Pell (and I still don't understand it), so I quit at that point and used a spreadsheet.

[ralphmerridew]

Quick discussion of Fermat-Pell equation:
For given N, solve x^2 - Ny^2 = +- 1

Say that a number (a + b*sqrt(N)), where a and b are integers, determines a solution to the equation iff a^2 - Nb^2 = +- 1.

Note that if p and q determine solutions, then so does pq:
(p1 + p2 sqrt(N)) (q1 + q2 sqrt(N)) = (p1 q1 + N p2 q2) + (p1 q2 + p2 q1) sqrt (N)
= (p1 q1 + N p2 q2)^2 - N (p1 q2 + p2 q1) ^ 2
= (p1^2 q1^2 + 2 N p1 p2 q1 q2 + N^2 p2^2 q2^2) - N (p1^2 q2^2 + 2 p1 p2 q1 q2 + p2^2 q1^2)
= p1^2 q1^2 - N p1^2 q2^2 - N p2^2 q1^2 + N^2 p2^2 q2^2
= (p1^2 - N p2^2) (q1^2 - N q2^2)
= (+- 1)*(+- 1)
= +- 1

Next, if p determines a solution, so does 1/p. (similar).

If a nontrivial solution exists, define the generator as the smallest g > 1 such that g determines a solution. (skipping over that there is unique)

Consider any number p, p > 1, that determines a solution. Choose n as the integer such that g^n <= p < g^(n+1).
g^n, 1/g^n, p/g^n determine solutions (above)
g^n <= p < g^(n+1) implies 1 <= p/g^n < g. By definition of g, the only way that is possible is if p/g^n = 1, or p = g^n.

Similarly, all solutions determined by a p < 1 are of form p^(-n).

Now, finding that generator (if it exists), can be a bit tricky...

[Chuck]

For four digit house numbers, house 1189 out of 1681 qualifies.

[ralphmerridew]

Using the generator method, you can quickly find

1 of 1
6 of 8
35 of 49
204 of 288
1189 of 1681
6930 of 9800
40391 of 57121
235416 of 332928
1372105 of 1940449
7997214 of 11309768
46611179 of 65918161
271669860 of 384199200
1583407981 of 2239277041
9228778026 of 13051463048
53789260175 of 76069501249
313506783024 of 443365544448
1827251437969 of 2584123765441
10650001844790 of 15061377048200
...