An interesting question
Delve into the genius of Indian Mathematicians with this seemingly easy question
Imagine walking down a street lined with houses, each one numbered sequentially from 1 to n. Somewhere along this street lies a special house, let's call it house x. What makes x special is that the sum of all house numbers to its left is exactly equal to the sum of all house numbers to its right. If n is between 50 and 500, what are n and x?
We challenge you to tackle this problem below without using web resources. Share your thought process in the comments, whether or not you solve it. If you do, feel free to showcase your accomplishment! The solution is at the end of the article, so try your best before peeking.
This problem isn’t just a casual brain teaser. It was once presented to one of the greatest mathematical minds of all time, Srinivasa Ramanujan, by his friend and colleague, P.C. Mahalanobis. The story goes that Mahalanobis posed this challenge during one of their conversations. To his amazement, Ramanujan didn't just find the solution quickly; he provided a general method to solve such problems using continued fractions. Mahalanobis was astounded and asked how he did it. 'It is simple. The minute I heard the problem, I knew that the answer was a continued fraction. Which continued fraction, I asked myself. Then the answer came to my mind', Ramanujan replied.
But what exactly are continued fractions, and how do they connect to our street of houses? Let's explore this concept briefly before we get back to solving our intriguing problem. Now if you read the definition of continued fractions you’ll probably be left more confused than you are now. So let us just look at an illustration to help you understand it.
Continued fractions may be finite or infinite. For infinite continued fractions in the above illustration we just put
and done. While this is not quite everything about continued fractions, there’s no need to delve in too deep to continue. Reading the problem again, there seems to be no apparent connection between continued fractions and the question or is there?
Let us try solving the problem and developing a methodology to solve for all n.
Either n is even or (n+1) is even, also GCD of n and (n+1) is 1 since 2 consecutive numbers cannot have any common factors other than 1.
Equation 1.1 then simplifies to
Again we observe that the GCD of m and ((2m+1) or (2m-1)) is 1 since the GCD of 2m and ((2m+1) or (2m-1)) is 1 and hence no factors of 2m can have a common factor with ((2m+1) or (2m-1)). Since the GCD of m and ((2m+1) or (2m-1)) is 1 and x is a positive natural number, m and ((2m+1) or (2m-1)) both need to be perfect squares for the above equation to hold. Let
Where a and b are positive integers. Then
So finding positive integer solutions a and b to the above equations such that the inequalities for n and x are satisfied gives us the solution to the problem.
Equation 1.5 has a special name. It is called Pell’s equation or the Pell-Fermat equation. Though it is named after Pell the equation was first studied extensively in India starting with Brahmagupta. Bhaskara II in the 12th century is generally credited with developing the chakravala method (a method which helps solve Pell’s equation), building on the work of Jayadeva and Brahmagupta. While these equations and topics are pretty interesting they do get somewhat complicated. So without going too much into the specifics of what methods are used to solve Pell’s equation we’ll describe how to solve this problem.
First observe that (3,2) is a solution to the above equation. This is a fundamental solution. Now all solutions to the above equation are given by
setting k=2 we get a=(3p+4q)=17 and b=(2p+3q)=12. a=17 and b=12 in the positive part of equation (1.4) which gives x=204 and n=288. And we can continue to get more solutions for x and n not bounded by the inequalities by repeating this process for a and b by substituting k=2 and the solution of the previous iteration in the above equation. Similarly identifying the fundamental solution (1,1) to the negative part of equation (1.4) and applying the above formula yields the another set of solutions to the question. But wait where is the continued fraction? Equation (1.6) or rather equation (1.7) has a special connection with something called the Pell numbers. Pell numbers are an infinite sequence of integers that provide a rational approximation to
If (a,b) is a solution of equation (1.7) then their ratio (a/b) provides an approximation to
The sequence of approximations of this form is
where the denominator of each fraction is a Pell number and the numerator is the sum of a Pell number and its predecessor in the sequence. That is, the solutions have the form
Now again you might wonder where exactly do continued fractions come into the picture. So let’s see how continued fractions enter the picture.
and so on till infinity, the process can be iterated till infinity. But terminating it after a finite number of steps gives us an expression of the form
And this is in the form of (a/b) where a and b are solutions to equation (1.7) and hence by terminating the continued fraction of
after a finite number of iterations gives rise to different pairs of a and b which determine x=ab and we can solve for n by solving the equation (1.1). Complicated yet simple isn’t it? This was Ramanujan’s wonderful solution, something he computed in his head within a few minutes, giving the answer for all values of x and n.