Ramanujan’s Continued Fraction!

The popular English magazine Strand had long carried a page, entitled “Perplexities,” devoted to intriguing puzzles, numbered and charmingly titled, like “The Fly and the Honey,” or “The Tessellated Tiles,” the answers being furnished the following month. Each Christmas, though, “Perplexities” expanded, the author fitting his puzzles into a short story.
Now, in December 1914, “Puzzles at a Village Inn” took readers to the imaginary town of Little Wurzelfold, where the main topic of interest was what had just happened in Louvain.

In late August, pursuing an explicit policy of brutalization against civilian populations, German troops began burning the medieval Belgian city of Louvain, on the road between Liege and Brussels. House by house and street by street they set Louvain to the torch, destroying its great library, with its quarter million books and medieval manuscripts, and killing many civilians. The burning of Louvain horrified the world, galvanized public opinion against Germany, and united France, Russia, and England more irrevocably yet. “The March of the Hun,” English newspapers declared. “Treason to Civilization.” It was an early turning point of the war, doing much to set its tone. Louvain came to symbolize the breakdown of civilization. And now it reached even the “Perplexities” page of Strand.

One Sunday morning soon after the December issue appeared, P. C. Mahalanobis sat with it at a table in Ramanujan’s rooms in Whewell’s Court. Mahalanobis was the King’s College student, just then preparing for the natural sciences Tripos, who had found Ramanujan shivering by the fireplace and schooled him in the nuances of the English blanket. Now, with Ramanujan in the little back room stirring vegetables over the gas fire, Mahalanobis grew intrigued by the problem and figured he’d try it out on his friend.

“Now here’s a problem for you,” he yelled into the next room

“What problem? Tell me,” said Ramanujan, still stirring. And Mahalanobis read it to him.

“I was talking the other day,” said William Rogers to the other villagers gathered around the inn fire, “to a gentleman about the place called Louvain, what the Germans have burnt down. He said he knowed it well — used to visit a Belgian friend there. He said the house of his friend was in a long street, numbered on this side one, two, three, and so on, and that all the numbers on one side of him added up exactly the same as all the numbers on the other side of him. Funny thing that! He said he knew there was more than fifty houses on that side of the street, but not so many as five hundred, I made mention of the matter to our parson, and he took a pencil and worked out the number of the house where the Belgian lived, I don’t know how he done it.”

Perhaps the reader may like to discover the number of that house.

Through trial and error, Mahalanobis (who would go on to found the Indian Statistical Institute and become a Fellow of the Royal Society) had figured it out in a few minutes. Ramanujan figured it out, too, but with a twist, “Please take down the solution,” he said — and proceeded to dictate a continued fraction, a fraction whose denominator consists of a number plus a fraction, that fraction’s denominator can consisting of a number plus a fraction, ad infinitum. This wasn’t just the solution to the problem, it was the solution to the whole class of problems implicit in the puzzle. As stated, the problem had but one solution — house no. 204 in a street of 288 houses; 1+ 2 + … + 203 = 205 + 206 + … + 288. But without the 50-to-500 house constraint, there were other solutions. For example, on an eight-house street, no. 6 would be the answer: 1+2+3+4+5 on its left equaled 7+8 on its right. Ramanujan’s continued fraction comprised within a single expression all the correct answers.

Mahalanobis was astounded. How, he asked Ramanujan, had he done it?

“Immediately I heard the problem 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.”

From The Man Who Knew Infinity, by Robert Kanigel

I will follow up this post, with a description of how Ramanujan may have solved it, using Pell’s equation.

Follow up:

Prof John Butcher, in his Mathematical Miniatures, has an excellent account of the solution, using Pell’s Equation, entitled “On Ramanujan, continued fractions and an interesting street number”. Check it here.
I am sure Prof Butcher’s page on Mathematical Miniatures and Apologies would also be of great interest!

The Evolution of Co-operation, by Robert Axelrod

Just finished reading this wonderful book by Robert Axelrod. I was first introduced to this book by a scientist from Microsoft Research, who gave a talk at IISc, almost entirely focussing on this book.

The crux of the book is what is known as the Iterated Prisoners’ Dilemma, which simulates the way in which fundamentally selfish agents behave. The heart of IPD is a pay-off matrix, which details the pay-offs for mutual co-operation, as well as defection. This presents a long-term incentive for co-operation as well as a short-term incentive for defection. It fits (casts) several real-world problems as an IPD and discusses very interesting scenarios. One of the scenarios that is indeed striking is when during the World War II, there existed a co-operative tie between warring factions, when the two camps used to fire at each other, but deliberately off-target, both indicating the potential for defection as well as the incentive to co-operate. Several interesting scenarios in biology and trade are also highlighted.

Tit for tat
Of all the computer programs that participated in Axelrod’s contest, Tit for Tat (which works by co-operating to begin with and reciprocating the opponent’s previous move in the rest of the moves) was the winner. There was also a second edition of the contest, with all information about the first one being made public, and (not so?) surprisingly, Tit for Tat finished first again! There is a lot of discussion about Tit for Tat in the book.

The Importance of being Nice(st)
Another observation in the results of the contests was that the nicer rules, i.e. the more forgiving rules, mostly performed better. Coincidentally, there was also a paper in Nature, yesterday that discusses the importance of being nice and ‘non-punishing’.

There is a small summary of interesting findings in the book, which I shall try and update soon…

Overall, it’s an amazing book that you would not want to miss out!

Also see http://en.wikipedia.org/wiki/The_Evolution_of_Cooperation

A funny derivation

Every new scientist must learn early that it is never good taste to designate the sum of two quantities in the form:

1 + 1 = 2                                               \qquad (1)

Anyone who has made a study of advanced mathematics is aware that:

1 = \mathop{ln} e

1 = \sin^2 x + \cos^2 x

2 = \sum_0^\infty \frac{1}{2^n}

Therefore eq. (1) can be expressed more scientifically as:

\mathop{ln} e + \sin^2 x + \cos^2x = \sum_0^\infty \frac{1}{2^n} \qquad (2)

This may be further simplified by use of the relations:

1 = \cosh y \sqrt{1 - \tanh^2 y}

e = \lim_{z->\infty} ( 1+\frac{1}{z} )^z

Equation (2) may therefore be rewritten as:

\mathop{ln}{\lim_{z->\infty} \left(1+\frac{1}{z}\right)^z} + sin^2 x + cos^2 x = \sum_0^\infty \frac{\cosh y \sqrt{1 - \tanh^2 y}}{2^n} \qquad (3)

At this point it should be obvious that eq. (3) is much clearer and more easily understood than eq. (1). Other methods of a similar nature could be used to clarify eq. (1), but these are easily divined once the reader grasps the underlying principles.

Golden Ratio

In mathematics and the arts, two quantities are in the golden ratio if the ratio between the sum of those quantities and the larger one is the same as the ratio between the larger one and the smaller.

\frac{\varphi+1}{\varphi}=\varphi

\varphi^2 - \varphi - 1 = 0

\varphi = \frac{1 + \sqrt{5}}{2}\approx 1.61803\,39887\dots\

\varphi = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\ddots}}}}

\varphi = \sqrt{1+\sqrt{1+\sqrt{1+\cdots}}\infty}

Some of the greatest mathematical minds of all ages, from Pythagoras and Euclid in ancient Greece, through the medieval Italian mathematician Leonardo of Pisa and the Renaissance astronomer Johannes Kepler, to present-day scientific figures such as Oxford physicist Roger Penrose, have spent endless hours over this simple ratio and its properties. But the fascination with the Golden Ratio is not confined just to mathematicians. Biologists, artists, musicians, historians, architects, psychologists, and even mystics have pondered and debated the basis of its ubiquity and appeal. In fact, it is probably fair to say that the Golden Ratio has inspired thinkers of all disciplines like no other number in the history of mathematics.

— Mario Livio, The Golden Ratio: The Story of Phi, The World’s Most Astonishing Number

(Almost all the above information is from wikipedia… I just wanted to populate this article at the moment; the golden ratio has been quite a fascinating constant! I have this Livio book, but haven’t had a chance to read it yet!)

Companion Matrix

The companion matrix of the monic polynomial p(t)=c_0 + c_1 t + \dots + c_{n-1}t^{n-1} + t^n is the square matrix defined as:

C(p)=\begin{bmatrix} 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -c_{n-1} \\ \end{bmatrix}.

p(t) is also the characteristic polynomial for the matrix. The eigenvalues for the above matrix are the roots of p(t).

I found this to be quite an interesting way to find the roots of any equation, with a great deal of ease! The corresponding MATLAB function is compan.

\mathbf{F} = \textrm{compan}([1 -1 -1]) = \begin{pmatrix} 1 & 1\\ 1 & 0 \\\end{pmatrix}

\begin{pmatrix} F_{k+2} \\ F_{k+1} \\ \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \\\end{pmatrix} \begin{pmatrix} F_{k+1} \\ F_{k} \\ \end{pmatrix}

Here, F_k is the kth; Fibonacci number.

The Man Who Knew Infinity, by Robert Kanigel

No wonder, this book is on on the great Donald Knuth’s reading list!

What a wonderful book this is… full of Ramanjuan’s exploits, told with an exquisite touch of admiration for Ramanujan and in wonderful detail. I’ve been wanting to review this book, but found a wonderful review elsewhere, which more than states what I would have.

Let me just put forth a few excerpts from the review first:


When it comes to biographies, I personally find it a delight when the author is overwhelmed by the person he is writing about, because it is then that you get to see hidden visages of the person. Robert Kanigel’s book is replete with such engaging depictions..“When he thought hard, his face scrunched up, his eyes narrowed into a squint. when he figured something out, he sometimes seemed to talk to himself, smile, shake his head with pleasure. When he made a mistake, too impatient to lay down his slate-pencil, he twisted his forearm towards his body in a single fluid motion and used his elbow, now aimed at the slate, as an eraser…”Ramanujan used a slate for working out his mind-boggling results and began entering the concise results themselves in notebooks. These notebooks have nothing short of a cult status in mathematical circles. They have helped pure mathematics branch off into stunning new fields, inspired thousands of research papers and are still being plumbed for their depth after a hundred years.

Hardy paid the ultimate tribute to Ramanujan during one of his lectures. He summarized, “Suppose that we rate mathematicians on the basis of pure talent on a scale from 0 to 100, I give myself a modest 25, Littlewood 30, the great Hilbert 80 and Ramanujan 100.


Apart from Ramanujan, this book also adequately addresses the Hardy, with a whole chapter devoted to him. It’s quite funny to read about Hardy’s love of cricket, his atheism, and above all his passion for math.In a postcard to his friend, Hardy (during the 1920s) listed six New Year wishes:
(1) prove the Riemann hypothesis;
(2) make 211 not out in the fourth innings of the last Test Match at Oval;
(3) find an argument for the non-existence of God which shall convince the general public;
(4) be the first man at the top of Mount Everest;
(5) be proclaimed the first president of the USSR or of Great Britain and Germany;
(6) murder Mussolini.

I’ll try and add some more snippets from the book, but be assured that it is a book that must adorn the library of any math enthusiast!

Bailey-Borwein-Plouffe formula

The Bailey-Borwein-Plouffe formula (BBP formula) provides a spigot algorithm for the computation of the nth digit of \pi. The original BBP \pi summation formula was found in 1995 by Plouffe using PSLQ. It is

\pi = \sum_{k = 0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right)

Amazingly, this formula is a digit-extraction algorithm for \pi in base 16.

It appears that there is a digit extraction algorithm even for e!

Most Beautiful Math Equations

This is a (subset of the) list of the most beautiful math equations ever derived, according to Ed Pegg Jr and Eric Weisstein (Mathworld). You can check the whole list here.

Archimedes’ Recurrence Formula
Let a_n and b_n be the perimeters of the circumscribed and inscribed n-gon and a_{2n} and b_{2n} the perimeters of the circumscribed and inscribed 2n-gon. Then
a_{2n}=\frac{2 a_n b_n}{a_n+b_n}, \quad b_{2n}=\sqrt{a_{2n}b_n}, \quad a_\infty=b_\infty
Successive application gives the Archimedes algorithm, which can be used to provide successive approximations to \pi.

Euler Formula
e^{i\pi}+1=0
This equation connects the fundamental numbers i, \pi, e, 1, and 0, the fundamental operations +, \times, and exponentiation, the most important relation =, and nothing else. Gauss is reported to have commented that if this formula was not immediately obvious, the reader would never be a first-class mathematician.

Euler-Mascheroni Constant
The Euler-Mascheroni constant gamma, sometimes also called `Euler’s constant’ or `the Euler constant’, is defined as the limit of the sequence
\gamma    =    \lim_{n \rightarrow \infty}\left(\sum_{k=1}^n \frac{1}{k}-\ln n\right)

\gamma has the numerical value 0.577215664901532860606512090082402431042…

Riemann Hypothesis
The Riemann hypothesis is a deep mathematical conjecture which states that the non-trivial Riemann zeta function zeros, i.e., the values of s other than -2, -4, -6, \ldots such that \zeta(s)=0 (where \zeta(s) is the Riemann zeta function) all lie on the “critical line” \sigma=\mathbb{R}[s]=1/2 (where \mathbb R[s] denotes the real part of s).

The Riemann zeta-function \zeta(s) is the function of a complex variable s initially defined by the following infinite series:

\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}

The Riemann hypothesis can be stated as:
\zeta(\alpha+i\beta)=0 and \beta \neq 0 implies \alpha=\frac{1}{2}.

Gaussian Integral
The Gaussian integral, also called the probability integral is the integral of the one-dimensional Gaussian function over (-\infty,\infty)

\int_{-\infty}^{\infty}{e^{-x^2}dx} = \sqrt{\pi}

totient?

Just thought of starting up a blog on math. I expect to put hear real arbit stuff on math that interests me and other math enthusiasts too!

Why totient? Basically wanted the title to be some glorious mathematical symbol. Then thought of functions. The totient function certainly seemed the most exotic one. Mustn’t everything beautiful in math have something to do with Euler or Gauss? I chose Euler for the moment, but I am sure to have interesting posts on all the other geniuses like Gauss, Fermat, Galois or Ramanujan, to name a very few, and maybe even Knuth(!) or Wiles.

But the question remains — “Did Euler ever envision applications in cryptography for his seemingly innocuous function?”.

Now to the introduction of the totient function:

In number theory, the totient \phi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.