- A certain street has between 50 and 500 houses in a row, numbered 1, 2, 3, 4, … consecutively. There is a certain house on the street such that the sum of all the house numbers to the left side of it is equal to the sum of all the house numbers to its right. Find the number of this house.
The story behind this problem is as follows. A friend of Ramanujan, P. C. Mahalanobis, who was also a student at Cambridge and who later became an eminent statistician, read about this problem while visiting Ramanujan. Ramanujan was in the kitchen, cooking. Mahalanobis solved the problem, and then turned to Ramanujan and said, “Here’s a problem for you.” “What problem? Tell me,” said Ramanujan, still stirring vegetables. Mahalanobis read the problem. Ramanujan immediately said, “Take down the solution.” He then dictated a continuous fraction that expressed all the infinite solutions to the problem if you ignore the constraint of 50 to 500 houses. So as a bonus problem, can you emulate Ramanujan and find a formula that generates this general solution?
As usual, Quanta readers responded magnificently to this puzzle, obtaining the correct answer (house number 204, on a street with 288 houses) using a variety of methods. With simple algebra, it is easy to obtain the equation 2h2 = n(n + 1), where h is the house number, and n is the total number of houses. This is an equation with an infinite number of integer solutions (the general name for an equation requiring integer solutions is Diophantine equation). We now have to find integer solutions with n in the range 50 to 500, which can be done by using a brute-force search using a spreadsheet, or by computer programming, as several readers did. Another approach is to start small — it is quite easy to find solutions to the above equation for small numbers such as h = 1, n = 1 followed by h = 6, n = 8. From this you can find a simple recurrence relation between h and n, or between successive h’s or n’s, using standard techniques for recurrences, as Greg Egan did. This yields all the infinite solutions recursively. Amazingly, Tom Nichols was able to derive a closed-form solution using the time-honored technique of playing with the numerical solutions. Congratulations, Tom! The young Ramanujan would have approved!
The first step to finding the solution without using trial-and-error methods is to recognize that the equation we obtained above can be expressed as a Pell equation of the form nx2 + 1 = y2, as described below. There are two well-known ways to solve these kinds of equations. The first, which doesn’t use continued fractions, is a method based on work done by the Indian mathematician Brahmagupta a thousand years before Pell, and transformed into a general method called the chakravala, or cyclic, method by Bhaskara II in the 12th century. The second method is based on continued fractions, the complete theory of which was perfected by Lagrange in the 18th century.
This brings us back to the bonus question. What is the continued fraction that Ramanujan came up with? Just by inspecting our equation, we can see that the ratio n:h will approach 2–√ as n and h increase indefinitely. The continued fraction for 2–√ is [1; 2, 2, 2, 2, …]. As Greg Egan described, this does yield the solutions, but not elegantly — you have to perform different operations on the odd and even convergents, and the solutions are not in order. A better approach derives the Pell equation and is described by Christopher Long:
Let there be n houses and let m be the excluded house, then the sum of 1 + … + (m – 1) must equal 1/2 of the sum of (1 + … + n) – m. This gives m(m – 1)/2 = n(n + 1)/4 – m/2 or 2m^2 = n(n + 1). Now complete the square on the right and we have 2m^2 + 1/4 = (n + 1/2)^2; finally, multiply by 4 to get (2n + 1)^2 – 8m^2 = 1. This is equivalent to solving the Pell equation x^2 – 8*y^2 = 1, as x must be odd. Solutions for x, ycan be generated from the continued fraction for sqrt(8) = [2; 1, 4, 1, 4, …].
This is definitely a better continued fraction for this problem. The convergents are 2, 3, 14/5, 17/6, 82/29, 99/35, 478/169, 577/204, … The denominators of every even-numbered convergent give the house numbers in succession, and their numerators (n) give the number of houses as (n – 1)/2.
This is good, but is there a better answer that Ramanujan might have come up with? It hasn’t been recorded, and I can’t look into his mind, but there is a more elegant answer. To see it, notice that the ratio 2n + 1 to h in this problem starts out at 3 and must decrease every time in succession — it must get monotonically closer to 8–√ as n and h increase. The convergents of the above continued fraction, on the other hand, oscillate from one side of the limit value to the other, which is why its odd-numbered convergents have to be discarded. How can we correct this? Well, there is a noncanonical form of the continued fraction for 8–√ that does do that: [3; –6, 6, –6, 6, –6, 6, …]. The convergents of this continued fraction are precisely successive solutions to the problem: 3, 17/6, 99/35, 577/204, etc. Here is how the continued fraction looks when written out in full in elegant, albeit slightly nonstandard, form:
From this continued fraction, it is easy to derive the recurrence hn+1 = 6hn – hn-1, which was described by Tom Nichols and Michael, and the corresponding recurrence for n, posted by Sudhir Kumar. From standard continued fraction theory we can easily derive the quadratic equation mentioned by Michael, x2 = 6x – 1. The theory also gives an elegant closed-form solution ((3+8–√)k) that you can write down directly, just by inspecting the continued fraction. If you carry out this expansion, and gather and add all the like terms, the multiplier of the radical gives h, the house number, and the integer part gives the number 2n + 1, where n is the number of houses. If we want to separate the two, we can obtain the following closed forms from this:
The latter is a simpler version of the same closed form obtained by Tom Nichols.
Thank you, everyone, for the great comments. I feel compelled to award two Quanta T-shirts this time: one to Tom Nichols for his discovery of the closed form, and the other to Christopher Long for his solution of the Pell equation. If this column has stimulated your interest in continued fractions, there is an excellent tutorial online.