Ramanujan And Mahalanobis

Number Theory Level 5

In 1914, Ramanujan 's friend P. C. Mahalanobis gave him a problem he had read in the English magazine Strand . The problem was to determine the number $x$ of a particular house on a street where the houses were numbered $1,2,3,\ldots,n$ . The house with number $x$ had the property that the sum of the house numbers to the left of it equaled the sum of the house numbers to the right of it. The problem specified that $50 < n < 500$ .

Ramanujan quickly dictated a continued fraction for Mahalanobis to write down. The numerators and denominators of the convergents to that continued fraction gave all solutions $(n,x)$ to the problem $($ not just the particular one where $50 < n < 500).$ Mahalanobis was astonished, and asked Ramanujan how he had found the solution.

Ramanujan responded, "...It was clear that the solution should obviously be a continued fraction; I then thought, which continued fraction? And the answer came to my mind."

This is not the most illuminating answer! If we cannot duplicate the genius of Ramanujan, let us at least find the solution to the original problem. What is $x$ ?

Bonus: Which continued fraction did Ramanujan give Mahalanobis?

This anecdote and problem is taken from The Man Who Knew Infinity , a biography of Ramanujan by Robert Kanigel.

The answer is 204.

3 solutions

Mark Hennings
Feb 24, 2016

The sum of the numbers less than $x$ is $\tfrac12x(x-1)$ . The sum of the numbers greater than $x$ is $\tfrac12n(n+1) - \tfrac12x(x+1)$ . We want these sums to be equal, which means that we want $\tfrac12n(n+1) = x^2 \;.$ Since $n$ and $n+1$ are coprime, this means that the set $\{n,n+1\}$ must be of the form $\{p^2,2q^2\}$ for integers $p,q$ . Thus $p,q$ must be solutions of Pell's equation $p^2 - 2q^2 = \pm 1$ .

The positive integer solutions of Pell's equations are the integer pairs $p_n,q_n$ , where $p_n + q_n\sqrt{2} \; = \; (1 + \sqrt{2})^n \;, \qquad \qquad n \in \mathbb{N} \;.$ and the corresponding value of $x$ will be $p_nq_n$ . The only solution with $50 < x < 500$ arises when $n=4$ , so that $p_n = 17$ , $q_n = 12$ , and hence $x = \boxed{204}$ and $n = 288$ .

Solutions to Pell's equation arise from convergents to the continued fraction expansion of $\sqrt{2} \,=\, [1,\overline{2}]$ .

How do you prove that these are the "only" solutions for the Pell's Equation? I mean that how does one know that all solutions are of the form $(1+√2)^{n}$

Arihant Samar - 5 years, 3 months ago

The simplest proof is to start by noting that the only number $x = a + b\sqrt{2}$ with $a,b \in \mathbb{Z}$ and $1 \le x < 1 + \sqrt{2}$ and $|a^2 - 2b^2| = 1$ is $x=1$ . This is done in various stages:

if $a < 0$ then $b\sqrt{2} \ge 1-a > 0$ , so that $2b^2 \ge 1 - 2a + a^2 > 1 + a^2$ , and hence $|a^2 - 2b^2| > 1$ .
if $b<0$ then $a \ge 1 - b\sqrt{2}$ , and we can show that $|a^2 - 2b^2| > 1$ similarly.
thus $a,b \ge 0$ . If $b \ge 2$ then $x > 1+\sqrt{2}$ , and so $b = 0,1$ .
if $b=1$ then $a<1$ , so $a=0$ . But this is not a solution.
thus $b=0$ , and hence $a=1$ .

Next you need to know that if $(a+b\sqrt{2})(c+d\sqrt{2}) = e+f\sqrt{2}$ , then $(a^2-2b^2)(c^2-2d^2) = e^2 - 2f^2$ . Just check the algebra.

If $x = a + b\sqrt{2}$ is such that $(1+\sqrt{2}) \le x < (1 + \sqrt{2})^2$ and $|a^2 - 2b^2| = 1$ , then $x(\sqrt{2}-1)$ would be of the form $c + d\sqrt{2}$ with $|c^2 - 2d^2| = 1$ and $1 \le x(\sqrt{2}-1) < 1 + \sqrt{2}$ , and hence would be equal to $1$ . Thus $x = 1 + \sqrt{2}$ .

Proceeding inductively, we can show that the only number of the form $a + b\sqrt{2}$ with $|a^2 - 2b^2| = 1$ and $(1 + \sqrt{2})^n \le a + b\sqrt{2} < (1 + \sqrt{2})^{n+1}$ is $(1 + \sqrt{2})^n$ (for any positive integer $n$ ). Thus the only numbers of the form $a + b\sqrt{2}$ with $|a^2 - 2b^2| = 1$ and $a + b\sqrt{2} \ge 1$ are the numbers $(1 + \sqrt{2})^n$ for $n \ge 0$ .The numbers of this type lying between $0$ and $1$ are the inverses of these, namely the numbers of the form $(\sqrt{2}-1)^n$ for $n \ge 0$ .

The more sophisticated method lies in understanding how the continued fraction expansion of $\sqrt{2}$ generates the solutions of Pell's equation. That would take too long to set out here! Check out a book on Elementary Number Theory, if you are interested.

Mark Hennings - 5 years, 3 months ago

Thanks a lot.

Arihant Samar - 5 years, 3 months ago

This is nice. A fair amount of what you said above is also contained in the wiki on Pell's equation .

Patrick Corn - 5 years, 3 months ago

Same method

Aditya Kumar - 5 years, 1 month ago

I too did the same.Pells equation.Although recursions make it even easy to find solutions.For $x^2-8y^2=1$ .we could build up the recursions $y(k+1)=3y(k)+x(k)$ and $x(k+1)=3x(k)+8y(k)$

Spandan Senapati - 4 years ago

Why can't it be of the form {a p^2, 2a q^2 } ?

Kim Hyunsoo - 3 years, 4 months ago

Because $n$ and $n+1$ have no common factor, and hence $a$ must be $1$ .

Mark Hennings - 3 years, 4 months ago

What about the bonus?

Mr. India - 2 years, 1 month ago

The quotients $\frac{p_n}{q_n}$ are the convergents of the continued fraction expansion of $\sqrt{2}$ . See the final sentence of my solution - I have already answered the bonus part.

Mark Hennings - 2 years, 1 month ago

Can you please elaborate 'convergents'?

Mr. India - 2 years, 1 month ago

@Mr. India – Try here . A convergent of a continued fraction is what you get if you stop the infinite continued fraction after a finite number of steps. Thus the continued fraction expansion of $\sqrt{2}$ is $\sqrt{2} \; = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \ddots}}}}$ The convergents are $1= 1 \hspace{0.5cm},\hspace{0.5cm}1 + \frac{1}{2} = \frac32 \hspace{0.5cm},\hspace{0.5cm} 1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} \hspace{0.5cm},\hspace{0.5cm} 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12}$ and so on. If the $n$ th convergent is $\tfrac{p_n}{q_n}$ , where $p_n,q_n$ are coprime, then $p_n^2 - 2q_n^2 = (-1)^n$ .

Mark Hennings - 2 years, 1 month ago

@Mark Hennings – Thank you sir!

Mr. India - 2 years, 1 month ago

In the first line it should be {x(x+1)}/2

Deepanshu Yadav - 1 year, 5 months ago

No. I want the sum of numbers less than $x$ , not less than or equal to $x$ .

Mark Hennings - 1 year, 5 months ago

Ssame way as u did

Kaustubh Miglani - 5 years, 3 months ago

Arpan Sarangi
Apr 10, 2018

I will focus on the "bonus" part of the question. Given condition --->

n^2 + n = 2x^2

Write it as ---> (2n+1)^2 - 8x^2 = 1.

Then express 8^0.5 as the continued fraction [2;1,4,1,4,1,4,1,4,...] . (Do it yourself)

So the solution is given by -

((2n+1)/x) = [2;1,4,1,4,1,4,1,4,...] (See the wiki on Pell's Equation)

P.S. - I don't know LaTeX

Kalyan Na
Sep 19, 2016

I did same analysis till the co-prime part of n, n+1. After that given the fact the solution for x = pq. I just enumerated primes till 17 since 50 < n < 500, 17^2 = 289 17^2 - 1 = 288 = 12^2 * 2 q=12 x=pq=204

Ramanujan And Mahalanobis

This anecdote and problem is taken from The Man Who Knew Infinity , a biography of Ramanujan by Robert Kanigel.

The answer is 204.

3 solutions

0 pending reports