Three Puzzles Inspired by Ramanujan

Insights from the mathematical genius Srinivasa Ramanujan give us a number of ways to explore the infinite.

[No Caption]

Olena Shmahalo/Quanta Magazine

Save Save Save Save Save Save Save Save Save Save Save Save Save

Srinivasa Ramanujan’s story is part of mathematical folklore, one of the most romantic in the history of mathematics. He started as a poor self-taught clerk in India. Working alone, he discovered highly original and unknown mathematical results that were far ahead of his time. In 1913, he sent a letter filled with strange-looking mathematical theorems to G. H. Hardy, a mathematician at the University of Cambridge. Hardy, one of the world’s leading experts on number theory, later said that “some of [Ramanujan’s theorems] defeated me completely; I had never seen anything in the least like them before.” He was referring to results like the one below.

A monthly puzzle celebrating the sudden insights and unexpected twists of scientific problem solving. Your guide is Pradeep Mutalik, a medical research scientist at the Yale Center for Medical Informatics and a lifelong puzzle enthusiast.

Hardy arranged for Ramanujan to come to England, and the rest is history. The work that Ramanujan did in his brief professional life a century ago has spawned whole new areas of mathematical investigation, kept top mathematicians busy for their whole professional lives, and is finding applications in computer science, string theory, and the mathematical basis of black hole physics.

The mathematician Mark Kac divided all geniuses into two types: “ordinary” geniuses, who make you feel that you could have done what they did if you were say, a hundred times smarter, and “magical geniuses,” the working of whose minds is, for all intents and purposes, incomprehensible. There is no doubt that Srinivas Ramanujan was a magical genius, one of the greatest of all time. Just looking at any of his almost 4,000 original results can inspire a feeling of bewilderment and awe even in professional mathematicians: What kind of mind can dream up exotic gems like these?

Ramanujan indeed had preternatural insights into infinity: he was a consummate bridge builder between the finite and the infinite, finding ways to represent numbers in the form of infinite series, infinite sums and products, infinite integrals, and infinite continued fractions, an area in which, in the words of Hardy, his mastery was “beyond that of any mathematician in the world.” While most of Ramanujan’s results are far beyond the scope of this column, it turns out that we can get a flavor for some simple infinite forms using nothing more than middle-school algebra. Let’s embark on a journey to the infinite.

  1. Our first question is to prove the following equation involving an infinite nested radical. In 1911, Ramanujan sent the right-hand side of the following equation to a mathematical journal as a puzzle:

If you are intimidated by this at first sight, don’t be! As I mentioned above, you can prove this result with no more than middle-school algebra. All you need is the following elementary result:

(x + 1)2 = x2 + 2x + 1 = x(x + 2) + 1

Rearrange the terms to get: (x + 1)2 = 1 + x(x + 2)

Now if we substitute 2, 3 and 4 for x, we get:

32 = 1 + 2(4), 42 = 1 + 3(5), 52 = 1 + 4(6), …

And believe it or not, that’s all you need to prove the intimidating-looking result above. Can you do it?

  1. In our second question, we use basic algebra to prove that the famous golden ratio, phi, is equal to the infinite continued fraction shown below.

Again, no need to be intimidated! The neat thing about the continued fraction on the right is that it is self-similar all the way to infinity. That means that you can start anywhere and get exactly the same continued fraction, as shown in the picture below: The continued fraction in the red box is exactly the same as that in the blue box. Yes, as we saw in last month’s column, as far as infinity is concerned, a part can be equal to the whole.

Based on this observed equality, can you set up an equation for the continued fraction and solve it with some elementary algebra to show that it is equal to the golden ratio? Note that this value [(1 + √5)/2] is contained in Ramanujan’s far more elaborate result that Hardy said defeated him completely (top figure).

Our third puzzle was sent to me by the cosmologist Susan Larsen. It was originally published in The Strand Magazine in 1914.

  1. 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?

That’s it for the mathematical puzzles. The true puzzles of Ramanujan’s ability are psychological, and I’d love to get the views of Quanta readers on these.

What if Ramanujan had modern calculating tools? Ramanujan, like many other great mathematical geniuses such as Gauss, loved to play with specific cases, which he then built into general results. These geniuses did prodigious calculations by hand — Ramanujan used chalk on slate in his early days, erasing intermediate results with his elbow. Steven Wolfram has conjectured that if Ramanujan had modern calculating tools like Mathematica, “he would have been quite an adventurer — going out into the mathematical universe and finding all sorts of strange and wonderful things, then using his intuition and aesthetic sense to see what fits together and what to study further.” What do you think?

Where do you think Ramanujan’s results came from? When Mahalanobis asked him how he arrived at his solution to problem 3 above, Ramanujan reportedly said, “As soon as I heard the problem, I knew the answer was a continued fraction. I asked myself, ‘Which continued fraction?’ and the answer just came to me.”

How would 21st-century mathematics be different had Ramanujan lived a life of normal length? Tragically, Ramanujan died at age 32, after only about six years as a professional mathematician, during which his output was stupendous. The question has to be asked about all great mathematicians who died young (notably Évariste Galois, inventor of group theory, who died at 20 in a gun duel). How much poorer is the world of mathematics because of Ramanujan’s untimely death?

Happy puzzling! I look forward to your answers.

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt. (Update: The solution is now available here.) And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately).

Note that we may hold comments for the first day or two to allow for independent contributions.

Correction: This post was revised on July 14 to remove an extraneous “1+” in the first line of the continued fraction and an apocryphal reference to a dream of Ramanujan’s.

Correction: This post was revised on July 15 to say that Évariste Galois died in a gun duel at the age of 20, not 21.






View Reader Comments (66)

Leave a Comment

Reader CommentsLeave a Comment

  • Answer to your first question.
    <Thanks much for the hint>
    3^2 = 1 + 2*4 — (1)
    4^2 = 1 + 3*5 — (2)
    5^2 = 1 + 4*6 — (3)

    Replace the number 4 in (1) with its representation in (2)
    3^2 = 1 + 2 * sqrt (1 + 3*5) — (4)
    Replace the number 5 in (4) with (3)
    3^2 = 1 + 2 * sqrt ( 1 + 3*(sqrt(1 + 4*6)))
    Continuing so till infinity,
    3^2 = 1 + 2*sqrt (1 + 3*sqrt(1 + 4*sqrt(1 + 5… )..))
    Taking the square root,
    3 = sqrt (1 + 2*sqrt (1 + 3*sqrt(1 + 4*sqrt(1 + 5… )..)) ) ===> this is the original expression posted by Ramanujan.

    Answer to your second question.
    x = 1 + 1 / ( 1 + (1 / 1+ ..)

    it can be noted that the denominator of the expression on the RHS is still x since it extends to infinity.

    => x = 1 + 1/x
    => x^2 – x – 1 = 0. The solution to this quadratic equation will yield the value of x.

    x = (1 +/- sqrt (1 + 4)) /2
    x = (1 + sqrt(5))/2 or (1 – sqrt(5))/2

    But it is clear that x is positive, so we reject the second solution.
    => x = (1 + sqrt(5))/2

    Answer for your third question. This is a tad murky, I am left with an equation, where I am having to use brute force to find the solution. Nevertheless, this was my approach.

    Assuming the houses are numbered => 1, 2, 3, … ,n-1, n, n+1, n+2, …, n+k
    where, n is the house to which the sum of the left and right houses are equal.
    left house sum => (n-1)*n/2 —- (1)
    right house sum => total_house_sum – sum_of_n_houses
    => (n+k)(n+k+1)/2 – n(n+1)/2 —- (2)
    (1) = (2)
    the equations boil down to this after simplifying,
    n^2 – n*(2k+1) – k (K+1) = 0

    n = ((2k+1) +/- sqrt (8k^2 + 8k + 1))/2

    by iterating k between 50 and 500, I think for a total of 288 houses, n = 204. is one of the solutions. Please let know of a more deterministic approach. And I cannot begin to wonder about the infinite fraction that Ramanjujan would have concocted.

  • Hi, I'm not a mathematician, so forgive me if this is a silly question. For problem three, I was easily able to devise an equation with two variables, and solved it using the Solver feature of Excel, but that just seems to me to be guessing at the two variables until a set works. Is there a way to solve this more elegantly?

    My equation: 2n(n+1) – x(x+1) = 0 where n = the house number and x = the number of houses

  • I have very strong doubts that the average middle-school student can prove (in the mathematically accepted sense) that the answers to questions 1 and 2 are correct. In fact, already expressing the statement in a mathematically precise way requires a certain level of mathematical sophistication.
    E.g. a variation of the argument for 2) can be used to show that 1 + 2 + 4 + 8 +… = -1 (call the solution x; then x=1+2(1+2+4+…)=1+2x hence x=1+2x which has -1 as only solution).

  • First two puzzles are relatively simple.

    For the third puzzle, assume that the sum of first n houses, is same as the sum of n+2 to m houses (so that the house number n+1 is in the middle).

    sum of the houses on left = n*(n+1)/2
    sum of the houses on right = (m+n+2)*(m-(n+1))/2
    => n*(n+1) = (m+(n+1)+1)*(m-(n+1)) = (m+(n+1))*(m-(n+1)) + m – (n+1)
    => n*(n+1) + (n+1) = m*m – (n+1)*(n+1) + m
    => (n+1)*(n+1) = m*(m+1) – (n+1)*(n+1)
    => 2*(n+1)*(n+1) = m*(m+1)
    => (n+1)*(n+1) = m*(m+1)/2

    We observe that the right side is the sum of first m numbers. Square root of the sum is house number that is in the middle.

    I will frame my answer in terms of the number of houses.
    I will also rewrite the equation as
    n*n = m*(m+1)/2
    where m is the number of houses and n is the balancing house. Some of the initial solutions will be:
    8 (6)
    49 (35)
    288 (204)
    If P and M are two consecutive solutions (e.g. P=8, M=49) then I get
    M*6-P+2 as the next solution.
    For example,
    288*6-49+2 = 1681 (1189) as the next solution
    1681*6-288+2 = 9800 (6930) as the next solution.
    9800*6-1681+2 = 57121 (40931) as the next solution.
    I am not sure if these are the only solution

  • My ninth grade daughter got the following question in her pre calculus class:
    There are five students with different names. Each of them writes his name on a piece of paper folds it, and puts it in a basket. They than randomly pick a piece of paper from the basket. What is the probability that exactly one of them gets the paper with his own name.

    Question is can you compute the probability of exactly one person getting his name right if there were 15 (or 20) students.

  • 1. Continue with the premise that (x+1)^2 = 1 + x(x+2). If you set x to 2 and substitute, you have 3^2 = 1 + 2(4). Now take the square roots of both sides and you have 3 = √(1 + 2(4)). Substitute 4 with the square rooted form of our original premise of (x+1)^2 = 1 + x(x+2) and you can see the right hand of the equation start to form into Ramanujan's result. Continue this pattern of substituting in the values with the square rooted form of that first equation and you have Ramanujan's result!

    2. We can see that the continued fraction equation Φ = 1 + (1 / (1 + (1 / (1 + (1 / ….))) is self referencing and becomes recursive, as in it repeats its own definition. So we can generalize it as Φ = 1 + (1 / Φ). This becomes an equation which we can perform algebra manipulations on: so rewrite 1 / (1 + Φ) as (2 + Φ) / (1 + Φ) and then multiply both sides by (1 + Φ). Now we have a quadratic equation Φ^2 – Φ – 1 which we can solve for using the quadric formula. This gives a positive solution (1 +√5)/ 2, or the golden ratio!

    3. I believe the general solution is an approximation for √2 / 2 in the form of a continued fraction. Let m be the total number of houses on the street and n be the house we are looking for (the selected house number whose sum to the left equals the sum to the right). Then we can define the ratio n / m. After finding some specific solutions, we can see a pattern where the ratio n /m which will eventually converge to √2 /2 (for example the first case of n=6 and m=10 has a ratio of 3/4 or 0.75; the second case of n=35 and m=49 has ratio of 0.714, etc). So we can think of the problem as finding as continued fraction for √2 /2. Let √2 /2 be our Φ for this problem. Now working backwards (from our approach from problem 2) we can eventually settle on a general form of Φ = 1 – (1 / (2 + 2Φ)) = √2 /2. So this general solution can be used to find the specific case that fits our problem: using the third "iteration" of the continued fraction we get our ratio n / m to be 17:24. When this n/m is multiplied by the right scalar, we get m to fit within our goal of 50-500 houses. This approximation can be used to find infinite solutions to this problem.

    I almost doubt that if Ramanujan had modern computing tools he would have come up with even greater results. His natural intuition for how the integers operate and feel was the most important part of his method. Computers certainly would have helped him verify his results and explore some fields that almost require these tools, but I get the impression that for Ramanujan, natural feeling and curiosity and intuition were what motivated him and what allowed him to produce such wonderful results. Personally, I wonder if his creativity had also been captured in a medium outside of math like art or music or programming, that we could have more insights into how he thought and from a different perspective. Otherwise, how he was able to be so creative is up to anyone – we just know that it produce fantastic results!

  • 2) Solve x = 1+1/x. Only the larger of the two solutions is valid given that x>1 as evident from the first term of the continued fraction.
    3) Solve : N(N+1) = 2P*P, where N is the number of houses and P is the house number. There will be no common factors for N and N+1. So N and N+1 must themselves either be a perfect square or twice a perfect square. For the range specified the valid values are N=8, 49, 288 and the corresponding P is 6, 35, 204.

  • Update July 14, 2016 7:20 pm

    Two changes have been made in this article since it was originally published earlier today.

    1. An extraneous "1+" in the first line of the Ramanujan continued fraction has been removed. Thank you Luis, for pointing this out.

    2. Under the question "Where do you think Ramanujan’s results came from?" I had written:

    Ramanujan was very religious, and believed that his results came from a divine source: His family goddess, Namagiri (a form of Lakshmi, consort of Vishnu) sometimes gave them to him in his dreams. One such event was described by him as follows: "While asleep, I had an unusual experience. There was a red screen formed by flowing blood, as it were. I was observing it. Suddenly a hand began to write on the screen. I became all attention. That hand wrote a number of elliptic integrals. They stuck to my mind. As soon as I woke up, I committed them to writing.”

    The above paragraph has been removed.
    The first half of the above is true: It has been been attested by many people that Ramanujan credited the goddess Namagiri for inspiring his mathematical results in dreams. However we have been unable to find an authentic source for the specific dream described above, even though it has been quoted by others. If anyone does know of a reliable, authentic source for Ramanujan having described such a dream, please let us know.

    We will hold comments containing answers to the problems for a couple of days so that people can try the problems on their own. Please post your answers as comments here.

  • Problem : 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.
    I'm Tara and it's my solution (sorry because of my broken English!)
    ([email protected])[email protected][email protected]        
    We don’t know the number of all the houses, but it must be an integer number between 50 to 500, we know that that houses are numbered 1, 2, 3, … consecutively, right ?!

    And we’re looking for the certain house that the sum of all the house numbers numbers to the left side of it is equal to the sum of all the house numbers to its right (suppose it’s a golden house!)

    So the answer must contain two numbers, the number of all the houses in the street, and the number of that golden house !!

    Now we put “m” for the number of all the houses and “n” for the number of that golden house !

    Absolutely :

    50 < m < 500   
    1 < n < m 

    As a mathematical point we know that the sum of numbers from 1 to p is equal to (p*(p+1))/2,

    So the solution comes from this :

    Sum of numbers from 1 to (n-1) must be equal to sum of numbers from (n+1) to m

    In the language of Math is :

    ((n-1)*(n))/2 = (m*(m+1)) – (n*(n+1))

    So now our new problem is m(m+1)/2 = n^2 !

    We know 50 < m < 500 and one of these 451 numbers times its next number divided into two, is going to be a square number and that’s what we’re looking for !

    There three way ahead of us :

    THE CRAZY WAY (to check out all the 451 numbers by calculator!!)

    *** The programming way is to write and copy the below code :
    tara n = (x, n)
      where x = (n * (n+1)) / 2

    tsqrt (n, x) = (sqrt n, x)

    ns = map (tsqrt . tara) [50..500]

    isInt (x, _) = x == fromInteger (round x)

    xs = filter isInt ns

    main = print xs
    in the below internet link :

    *** The not programming way to solve m(m+1)/2 = n^2 for 50 < m < 500 is to say that :

    m(m+1)/2 for even m is m/2 * (m+1) (even*odd)

    m(m+1)/2 for odd m is m * (m+1)/2 (odd*even)

    So in any way m(m+1)/2 is multiplication of two numbers, one even and one odd,

    It’s obvious that if m(m+1)/2 is going to be a square number, EITHER each of the two numbers, I talked about in the last line, must be a square number itself OR the two numbers must be equal (means either m/2 = (m+1) that it’s impossible for natural m, or m = (m+1)/2 that the only answer for it is m=1 and we know that absolutely we have more than one house in the street!) , so the two numbers are not equal but each of them is itself a square number (for example we know that p*q=36, OR p+q=6, OR p=1, q=36, p=4, q=9 and so on)

    Let’s see where are we now !?

    We’re looking for a number between 50 to 500 named “m” that :

    For even m, m/2 and (m+1) are both square number,

    For odd m, m and (m+1)/2 are both square number,

    Let’s have a list of square numbers here :

    …, 81, 100, 121, 144, 169, 225, 256, 289, 324, 361, 400, …

    For the m we’re looking for :

    For even m, m/2 and (m+1) must be in the above list (means for one of the numbers in the above list, its twice plus one also must be in the list!),

    For odd m, m and (m+1)/2 must be in the above list (means for one of the numbers in the above list, the half  of its next consecutive number  also must be in the list!),

    Can you see 144 and 289 winking ?!

    Alright, so :

    m/2 = 144

    (m+1) = 289

    (And because the problem is supposed to have one answer, so I made sure that it’s the only answer!)

    Now we have m here :

    m = 288

    But what was m ?!

    It was the number of all the houses,

    But what about the number of that golden house !?

    Don’t worry !

    We had this equation :

    m(m+1)/2 = n^2

    so now we have n just here :

    n = 204

    Now close your eyes and imagine the street in which has 288 houses in a row named consecutively from 1 to 288, the 204th house is the golden house that satisfies the conditions !

  • Puzzle 1

    Suppose that:

    f(n) = sqrt(1 + n sqrt(1 + (n+1) sqrt(1 + (n+2) sqrt( …))))

    has a finite, well-defined value for any positive integer n. Then we have the recurrence relation:

    f(n)^2 = 1 + n f(n+1)

    But as the hint makes clear, this is solved by:

    f(n) = n+1

    The expression on the RHS in the question is f(2), so we have f(2)=3, in agreement with the statement to be proved.

    Puzzle 2

    If the value of the continued fraction is r, it obeys the equation:

    r = 1+1/r

    which can be obtained by setting both the blue and red boxes equal to r, since they enclose identical expressions. Writing this as a single fraction, it is equivalent to:

    (r^2–r–1)/r = 0

    By the standard formula for the roots of a quadratic, the only positive root of the numerator is:

    r = (1+sqrt(5))/2

    which is the golden ratio, as was to be shown.

    Puzzle 3

    Suppose we have N houses on the street, and the sum of the numbers of all the houses to the left of house H is equal to the sum of the numbers of all the houses to the right. There is a well-known formula for arithmetic series like these:

    S(n) = 1+ … + n = n(n+1)/2

    This is easily proved by adding two copies of the sum, one in the original order and one reversed, and noting that it consists of n terms all equal to (n+1).

    The claim about the houses can be rephrased as saying that if we double the sum we get from all the houses to the left of house H, the result will be exactly the same as adding up all the house numbers except for house H itself. That is:

    2 S(H–1) = S(N) – H

    Using our formula for S(n), this becomes:

    (H–1)H = N(N+1)/2 – H

    or equivalently:

    2 H^2 – N(N+1) = 0

    So we want to find integers that solve this. One solution for small values that can easily be found with a bit of trial and error is H=6, N=8. And if we guess that there might be some recurrence relation that gives us larger solutions as linear expressions of smaller ones, then with a bit of algebra it's not hard to show that:

    H' = 1+3H+2N
    N' = 1+4H+3N

    has the wonderfully simple property that:

    2 H'^2 – N'(N'+1) = 2 H^2 – N(N+1)

    So given any pair (H,N) that solves the problem, this lets us find a new pair, (H',N') that is also a solution. This easily gives us as many more solutions as we want, starting from (6,8):

    (6,8), (35,49), (204,288), (1189,1681), …

    OK, but how can we connect this problem to a continued fraction? First, we note that for large values of N, the expression N(N+1) is approximately N^2, so we would expect H/N to be approximately equal to sqrt(1/2). So we might get something useful from the continued fraction for sqrt(1/2).

    We begin with:

    sqrt(2)–1 = 1/(2+1/(2+1/(2+…)))

    This is easily verified in the same way we verified the continued fraction for the golden ratio, given that sqrt(2)–1 is the only positive solution of r=1/(2+r). Adding 1 and taking the reciprocal gives us the continued fraction for sqrt(1/2):

    sqrt(1/2) = 1/(1+1/(2+1/(2+1/(2+…))))

    The first few convergents of this are:

    2/3, 5/7, 12/17, 29/41, 70/99, 169/239, …

    It's not hard to see that there's a simple pattern that lets us go from one numerator and denominator to the next:

    n' = n+d
    d' = d+2n

    which follows from some simple algebra and the infinite sequence of 2s.

    Now, I don't know if Ramanujan had a better trick, but to find the house number solutions here I need to treat the odd and even entries in this sequence a little differently. For 5/7, 29/41, etc., we can write:

    H = n d
    N = d^2

    Then H/N = n/d, so as n/d gets close to sqrt(1/2), so will H/N. And we have:

    5/7 gives (35,49)
    29/41 gives (1189, 1681) etc.

    However, for 2/3, 12/17, 70/99 etc., we use a different formula:

    H = n d
    N = 2 n^2

    Then H/N = d/(2n). As n/d gets close to sqrt(1/2), this gets close to 1/(2 sqrt(1/2)) = sqrt(1/2), so again H/N approaches sqrt(1/2). And we have:

    2/3 gives (6,8)
    12/17 gives (204,288) etc.

    To prove that these two formulas really work however far we go, we need to iterate our recurrence formula, to see how we go to the fraction two steps along:

    n'' = n'+d' = 3n+2d
    d'' = d'+2n' = 3d+4n

    If we get H and N from our first formula, H = n d, N = d^2, we see that:

    2 H^2 – N(N+1) = d^2 (2n^2 – d^2 –1)

    But if we skip ahead two places in the list of fractions, and use the same rule, we get:

    2 H''^2 – N''(N''+1) = d''^2 (2n''^2 – d''^2 –1) = (3d+4n)^2 (2n^2 – d^2 –1)

    If the expression involving H and N is zero, we must have 2n^2 – d^2 –1 = 0, and the equivalent expression in H'' and N'' will also be zero. So, using the rule to convert the even numbered entries in the list of finite continued fractions into values of H and N, we know that we succeed for entry 2 in the list, 5/7, and we have proved that if we succeed for even entry m, we will succeed for entry m+2. So we have proved that this will work for every even entry in the list.

    Similarly, if we get H and N from our second formula, H = n d, N = 2n^2, we see that:

    2 H^2 – N(N+1) = 2 n^2 (d^2 – 2n^2 – 1)

    And if we skip ahead two places and use the same rule, we get:

    2 H''^2 – N''(N''+1) = 2 n''^2 (d''^2 – 2n''^2 – 1) = 2(3n+2d)^2 (d^2 – 2n^2 – 1)

    If the expression involving H and N is zero, we must have d^2 – 2n^2 – 1 = 0, and the equivalent expression in H'' and N'' will also be zero. So, using the rule to convert the odd numbered entries in the list of finite continued fractions into values of H and N, we know that we succeed for entry 1 in the list, 2/3, and we have proved that if we succeed for odd entry m, we will succeed for entry m+2. So we have proved that this will work for every odd entry in the list.

  • *mathematical equations are in LateX notation

    Solution to problem 1:

    Lets take a expression

    [X+N]^2 = X^2+2NX+N^2= N^2 + X[(X+N) + N]

    taking square roots on both sides,

    [X+N] = sqrt(N^2 + X* [(X+N)+N])

    substituting the term inside the big bracket (which is in the form of X+N) with the same equation, X+N replacing X

    X+N = sqrt(N^2 + X*sqrt(N^2 + (X+N)[(X+2N)+N]))

    repeating the same process infinitely, we get an infinite nested radical

    X+N = sqrt(N^2 + X* sqrt(N^2 + (X+N) sqrt(N^2 + (X+2N) sqrt(………..)………..)

    If, n = 1, x = 2,

    3 = sqrt(1 + 2 sqrt(1 + 3 sqrt(1 + 4 sqrt(………..)……………)

    Solution to problem 2:

    Let the entire expression(circled by red), be represented by X.

    X=1+ \frac{1}{1+\frac{1}{1+ \frac{1}{1+\frac{1}{1+ \frac{1}{1+\frac{1}{..…}}}}}}

    As the part of the expression which is circled in red is can be treated equal to the expression circled by blue.


    reduces to

    Evaluating the quadratic equation, we get,

    The negative solution can be eliminated as X can never be negative.
    The positive root evaluates to the golden ratio,

    Solution to problem 3:
    Let us suppose there are N houses in the street(between 50 and 500) and X be the number of a house.
    The problem can be represented by following equation,

    Using, the formula for, sum of natural numbers upto n : 0.5*(n)*(n+1)
    the equation becomes,

    The equation reduces to


    which is general equation that can be evaluated to find X without any constraints on N.

    The equation can also be written as.
    which is a Pell’s equation

    The unique solution for Pell’s equation A^2+d*B^2=1 for d=2 in the range

    A=>(2*50+1) and A<=(2*500+1) are,


    Therefore, the house numbered 84 (X=169/2)and 204(X=408/2) are the solution to the problem.

  • I believe that Ramanujan came up with the answer sqrt(2), which can be expressed as a continued fraction [1;2,2,…] which can be rewritten as 1 + 1/(2 + 1/(2 + 1/(2 + …))). The solution is encoded in this fraction, in the so called nth convergents. For instance:
    1 + 1/(2 + 1/2) is the 3rd convergent and is equal to a/b, where a = 7 and b = 5.
    By multiplying a and b, we obtain number of the house which 'divides' the rest of the houses into two groups. In this example, x = a*b = 35. How do we know how many houses are there in total (let's call this number n)?
    n = (-1 + sqrt(1+8x*x))/2
    If we rewrite the puzzle in terms of equations, we can obtain the aforementioned relation after a couple of steps. In this case n = 49, which does not fit the constraints.
    The next convergent is 1 + 1/(2 + 1/(2 + 1/2)), which equals to 17/12. By multiplying nominator and denominator we obtain x = 17*12 = 204 and n = 288. This solution fits the constraints. We can obtain an infinite number of solutions by taking convergents of higher order.
    I uploaded an image of a more detailed derivation under this link:

  • [Pradeep’s introduction to this comment:
    I didn’t mention in the article that two other things that motivated me to write this column were: First, I saw the film about Ramanujan “The Man Who Knew Infinity” which was released recently. The film is based on Robert Kanigel’s book of the same name. I highly recommend both the book and the film. Second, I had the opportunity to listen to and speak with Professor Ken Ono, the Emory University mathematician who like many top number theorists, was inspired by Ramanujan’s story and work. Dr. Ono has made hitherto unknown discoveries hidden in Ramanujan’s work related to such modern mathematical topics as Hall-Littlewood polynomials, modular forms, and the representation theory of Kac-Moody affine Lie algebras which form a deep hidden theory. In short, Dr. Ono discovered one of Ramanujan’s intuitive sources — the “motherlode” behind the results like the continued fraction shown above. Dr. Ono also found that Ramanujan had discovered a deep mathematical object called a K-3 surface decades before these objects were discovered and named, which accounted for his knowledge of the properties of the famous taxicab number, 1729. As one of the world’s top authorities on Ramanujan, Dr. Ono was also the mathematical consultant to the film. I asked Dr. Ono for his perspective on my final question, and here is his answer:]

    Your last question: How would 21st-century mathematics be different had Ramanujan lived a life of normal length?

    This is a very interesting question. Ramanujan would worked with people like Atkin, Hecke, Weil….and perhaps even Serre. Frankly, had he lived longer then it seems likely that virtually everything I have done in my career would have been known before I even set foot in college in the 1980s.

    [Thank you, Dr. Ono. I am sure you would then have made many more discoveries in a different and richer mathematical universe! Pradeep]

  • In the houses problem, do we include the house itself? i.e., if house n is the solution, is the the case that 1+2+3+…+n = (n+1)+(n+2)+(n+3)… etc? Or do we omit the n on the left hand side?

  • For question #3, there are 2 solutions. If the # of houses is 49 or 288, then houses 35 and 204 respectively will have the desired property.

    The way to find this is to say, given n houses, what is the sum of the half of the houses to the left of the guessed house, and to say that that must be equal to the sum of the houses to the left of your guess of the middle house.

    If you recall that the formula for the sum of the first k numbers is k*(k+1)/2, then you have all the algebra you need.

    If n is the number of houses, and g is the # of the guessed middle house, then:
    (Sum of all houses — the guessed middle house) / 2 = Sum of houses to left of guessed house
    = [ n*(n+1)/2 – g ] / 2 = (g-1)*[(g-1)+1]/2

    If you solve for g you get:
    g = sqrt[ (n^2 + n) / 2) ]
    So where this sqrt has a whole number solution for a given n, then n is the size of the neighborhood, and the solution g is the house number with equal sums to its left and right.

    For question 2, if you just look at the boxes you made, and say t is "the thing in that box", then 1/t + 1 = t.

    If you multiple both sides by t and rearrange, you get t^2 – t – 1 = 0. If you plug this into the quadratic formula (with a=1, b=-1, c=-1), you get:
    t = [ 1 + sqrt(5) ] /2
    which is the golden ratio.

  • I came across this about Ramanujan and the movie, " The man who knew infinity " ( ) Perhaps the Q & A mentions this site as well called the spirit of Ramanujan ( ) may be interest to Quanta Magazine readers and the puzzle solvers.

  • Call the total number of houses n, and the house in question x. The sum of numbers up to any number q is q(q+1)/2, so the sum of numbers up to house x-1 is (x-1)x/2.

    The sum on the right side of x is the sum up to n, minus x, minus the sum up to x-1. In symbols, this is n(n+1)/2 – x – (x-1)x/2.

    Equate the left sum with the right and cancel things and rearrange. You get:
    x^2 = n(n+1)/2, or x = sqrt(n(n+1)/2).

    A quick program or Excel spreadsheet shows that this works if n=288 and x=204.

    I have no idea how to write that sqrt expression in a continued fraction.

  • 1. From the hint you gave of (x+1)^2 = x(x+2) + 1, we can take the square root of both side and rearrange to get: x+1 = √(1 + x(x+2)). Plugging in x = y-1 gives us a form that's easier to recurse with: y = √(1 + (y-1)(y+1)). Leaving the (y-1) factor alone, we take the y+1 factor and find a new expression for it using the very same equation: y = √(1 + (y-1)√(1 + y(y+2))). Continuing this process inductively gives us Ramanujan's nested radical. (Since the first factor inside the radical times another radical is 2, we have y-1 = 2, or y = 3, solving the radical).

    2. Set the continued fraction equal to X so that X = 1+1/(1+1/(1+…)). As shown in your picture, the inner blue box is the same as the outer red box, so X = 1+1/X. Multiplying both sides by X and rearranging yields X^2 – X – 1 = 0. One of the roots of the quadratic is negative, so the solution must be the only positive solution: phi.

    3. Let N be the total number of houses, and n be the certain house whose left neighbors' sum equals their right neighbors' sum. The sum of the left neighbors' house numbers is (n-1)*n/2, and the sum on the right is N(N+1)/2 – n(n+1)/2. Setting them equal and moving all n's to the left hand side gives us n^2 = N(N+1)/2. For some integer A, if A divides N, then A does not divide N+1. That means that either N is a perfect square and N+1 is a perfect square times two, or N is a perfect square times two and N+1 is a perfect square. Making a table of the first 20 or so numbers along side their squares and twice their squares, it becomes apparent that N = 2*4, N+1 = 9 would yield n = 6, but the problem states that 50 <= N <= 500, so that solution is invalid. Next, N = 49, N+1 = 2*25, n = 25 also would work, though the N is too small. Finally, N = 2*144, N+1 = 289, n = 204 satisfies the constraint and solves the problem.

    As for the bonus question, I haven't found anything that works quite yet. The ratios of sucessive n's (or N's) seems to converge to some number (around 5.83), so potentially the convergents of a continued fraction of that number would yield ratios of successive solutions, but I haven't figured out how to calculate that number.

  • Consider continued fraction of sqrt(2) = 1+1/2+1/2+… ; consider the convergents, p/q then the special house, a = p * q, and number of houses = (-1+sqrt(1+8a^2))/2.
    Sample code:
    Solution for (50, 500) is 288.

    First 10 solutions:
    0 0
    1 1
    6 8
    35 49
    204 288
    1189 1681
    6930 9800
    40391 57121
    235416 332928
    1372105 1940449

  • On Puzzle 3, I just want to add that there are two trivial solutions for the house number, H, and the length of the street, N, that come before the first interesting solution, H=6, N=8. These are H=0, N=0 and H=1, N=1. The first might be debatable, since no house can be numbered zero in the statement of the puzzle, but it satisfies the equation 2 H^2 – N(N+1) = 0. The second, a street with a single house, is a bona fide solution, where the sum of the numbers of houses to both the left and right of the single house is zero.

    The nice thing, though, is that even these two trivial solutions fit in with all the usual formulas. The recurrence relation:

    H' = 1+3H+2N
    N' = 1+4H+3N

    can take us from H=0, N=0 to H'=1, N'=1, and from H=1, N=1 to H'=6, N'=8. So if we figured out the recurrence formula first, we wouldn't even need trial and error to find the (6,8) solution.

    These two trivial solutions also correspond to the first two convergents of the continued fraction for sqrt(1/2), which are 0/1 and 1/1. The 0/1 comes about because the general form is usually taken to be:

    A + 1/(B + 1/(C + 1/(D + … )))

    and for sqrt(1/2) we have A=0, B=1, C=D=…= 2. So the first two convergents are:

    A = 0/1
    A + 1/B = 1/1

    In the first case, n=0, d=1, we use the formula:

    H = n d
    N = 2 n^2

    that we use for 2/3, 12/17, 70/99, etc., to obtain H=0, N=0, and in the second case, n=1, d=1, we use the formula:

    H = n d
    N = d^2

    that we use for 5/7, 29/41 etc., to obtain H=1, N=1. I was a bit wary of trying to include the convergents that appear before the continued fraction settles into a pattern of repeating 2s, but in fact the recurrence formula for the numerators and denominators of the convergents:

    n' = n+d
    d' = d+2n

    works even in the first step, taking us from 0/1 to 1/1.

  • I have done a proof by induction for the 1st question rather than what you guys suggested, I found it easier to be honest haha. As it is a proof by induction I've uploaded some images to imgur rather than typing it out as it is a fairly long proof and I think it would be very confusing to type out. Anyway here is the link:

  • Second question:
    Let x = 1 + 1/(1+1/(1+1/…))
    Then x = 1 + 1/x
    So x^2 = x +1
    x^2 – x – 1 = 0
    x = (1 ± root(5))/2
    As x > 0, x cannot be (1-root(5))/2
    Therefore x = (1 + root(5))/2, which is the golden ratio, as required.

  • Not an infinite fraction, but I think it is the right answer (hopefully):

  • For 1, (x+1)^2 = 1+x(x+2) = 1+x*sqrt(1+(x+1)(x+3)) = 1+x*sqrt(1+(x+1)*sqrt(1+(x+2)(x+4)) etc. Now let x=2 to get Ramanujan's result.

    For 2, we have x = 1/x, and solving for x we get phi.

    For 3, let there be n house 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,y can be generated from the continued fraction for sqrt(8) = [2; 1, 4, 1, 4, …]. The first few convergents are 3/1, 17/6, 99/35, 577/204. Our desired solution comes from the last convergent, giving 288 houses and 204 the middle house.

  • 10=√(1+9√1+10√1+11√1+12√1+⋯)

    And Mr. Ken Ono, I am big devotee of Ramanujan and you. When I grow up more I want to work with you, Ramanujan was my first inspiration and in the present world you are my second inspiration, it will be my privilege to meet you.

  • 1.From the given identity, (x + 1)2 = 1 + x(x + 2)
    So 3 = √1+2(4) = √1+2(√1+3(√1+4(6)))
    = √1+2√1+3√1+4√…
    It was really interesting to see that we can write other numbers in the same way,
    like, 2= √1+1(√1+2(√1+3(√1+4(6))))

    2. Let (1+√5)/2 ≈ 1.6 = 1+0.6 = 1+6/10 = 1+1/(10/6)
    = 1+1/(1+4/6)

    We can write a longer continued fraction if we have more decimal places.

    So if we take,
    (1+√5)/2 ≈ 1.618 = 1+ 0.618 = 1+ (618/1000)
    = 1+1/(1+382/618)
    =1+1/(1+1/(1+1/(1+146/236))) …
    Thus with this method we can write as large continued fractions as we want.

    3.We have given houses between 50 to 500 or more clearly 1 to 448.
    If I start with some small numbers,
    1 2 3 4 5 (6) 7 8, then before and after number 6 the sum is equal.
    Similarly in 1 2 3 4 5 6 7 8 (9) 10 11 12 13, 9 is that number.

    In both of these the number is always greater by 2 from the central number (4 and 7). So in 1 to 448, the number before and after which the sum of all numbers will be equal should also be greater than 2 from 224. since (1+448/2) ≈ 224.
    So the number is 226.

  • For puzzle #3, assume that the desired house number is b and the number of the last house is c. The sum of the numbers of the houses on the left (from 1 to b-1) is

    L = b(b-1)/2

    and the sum of the numbers of house on the right (from b+1 to c) is

    R = (c+b+1)(c-b)/2

    Setting R equal to L results in

    c^2 + c = 2b^2

    I found a few integer solutions to this equation by brute force and started looking for patterns. I found some interesting ones, which you can see in this table.

    n b_n c_n b_n/b_n-1 c_n/c_n-1 b_n – K_n-1 b_n /K
    1 1 1
    2 6 8 6.00000 8.00000 1.71573E-01 1.02944E+00
    3 35 49 5.83333 6.12500 1.02944E+00 6.00505E+00
    4 204 288 5.82857 5.87755 6.00505E+00 3.50009E+01
    5 1189 1681 5.82843 5.83681 3.50009E+01 2.04000E+02
    6 6930 9800 5.82843 5.82986 2.04000E+02 1.18900E+03
    7 40391 57121 5.82843 5.82867 1.18900E+03 6.93000E+03
    8 235416 332928 5.82843 5.82847 6.93000E+03 4.03910E+04
    9 1372105 1940449 5.82843 5.82843 4.03910E+04 2.35416E+05
    10 7997214 11309768 5.82843 5.82843 2.35416E+05 1.37211E+06
    11 46611179 65918161 5.82843 5.82843 1.37211E+06 7.99721E+06
    12 271669860 384199200 5.82843 5.82843 7.99721E+06 4.66112E+07
    13 1583407981 2239277041 5.82843 5.82843 4.66112E+07 2.71670E+08
    14 9228778026 13051463048 5.82843 5.82843 2.71670E+08 1.58341E+09
    15 53789260175 76069501249 5.82843 5.82843 1.58341E+09 9.22878E+09

    Looking at the first 4 or 5 solutions, I found that the ratio of the nth solution to the n-1th solution, b_n/b_n-1, appears to converge to a constant K = 3 +2^(3/2) (approximately 5.83843) as n increases. This makes it easy to find other solutions – just multiplying the largest known solution by K and rounding to the nearest integer results in another solution.

    I wondered how much each solution differed from a power of K, so I calculated b_n – K(n-1) and b_n/K for each solution. That turned up another interesting relationship. It appears that b_n – K^(n-1) = b_n-1/K. A little recursive substitution with this equation results in

    b_n = K^(n-1) + K^(n-3) + . . . + K^(-n+3) + K^(-n+1) + 0

    The final term is b_n/K^(-n) which is zero. Seemingly miraculously, all of the irrational parts of this equation cancel out, leaving an integer for b_n. This is because

    1/K = (3 + 2^(3/2))-1 = 3 – 2^(3/2)

    The above expression for b_n is a geometric series and can be rewritten in closed form as

    b_n = (K^(n-1) – K^(-n-1)) / (1 – K^(-2))

    I conjecture that {b_n, n= 1, 2, 3, . . .} contains the complete set of solutions, and that b_n is a solution for every n, but I have so far I have failed to prove it. If it is, then it must be related to the continued fraction solution, but I have not found that relationship, either.

  • Here is a link to my table in MSWord format:

  • In puzzle 1 the problem doesn't clearly state what sequence to consider when taking the limit since you can end the expression for the m-th term in pretty much any way you choose. For the classic solution we have to choose

    a_m = √(1+2√(…√(1+(m-1)√(1+m(m+2)))))

    for then a_m is the constant sequence which equals three, and the limiting expression looks like √1+2√1+3√… as intended.

    To be sure we can prove that a_m=3 by induction. For the m=2 term we have

    a_2 = √(1+2(2+2)) = 3

    while for m>2, using the suggestion (m+1)^2=1+m(m+2) we find

    a_m = √(1+2√(…√(1+(m-1)√(1+m(m+2))))
    a_m = √(1+2√(…√(1+(m-1)√(n+1)²)))
    a_m = √(1+2√(…√(1+(m-1)(n+1)))) = a_(m-1)

    So a_m really is the constant 3. But there's something unnatural about the term (m+2). A less contrived choice to me is to simply stop writing the expression at some point:

    b_m = √(1+2√(1+3√(…√(1+m))))

    If this sequence indeed goes to three than I'll be happy. The best I could find though is that it does converge to a number between √3 and 3. It probably goes to three because b_10 is already almost 2.99.

    To prove it converges at all we can first see that b_m<a_m for every m>1. Starting from
    m<m(m+2) , and knowing that adding one, taking square roots and multiplying by positive numbers are monotonically increasing functions:

    1+m < 1+m(m+2)
    √(1+m) < √(1+m(m+2))
    (m-1)√(1+m) < (m-1)√(1+m(m+2))

    we eventually get
    √(1+2√(…√(1+m))) < √(1+2√(…√(1+m(m+2))))

    Which shows that b_m is bounded above by 3 since a_m=3.

    Similarly we can show that b_m<b_(m+1). This time we start with m < m√(1+(m+1)) and apply the same functions to each side to obtain
    √(1+2√(…√(1+m))) < √(1+2√(…√(1+m√(1+(m+1))))). This shows that b_m is a monotonically increasing sequence.

    Since b_n is bounded above and monotonically increasing we conclude that b_n indeed converges.

  • Seeing the continuing fraction solution, I can now relate my solution to it. I observed that in successive solutions, the house number increases by a factor that converges to 3 + 2^(3/2).

    The continued fraction used in the solution is given as

    2^(1/2) = 1+1/(2+1/(2+1/(2+. . .)))

    If the nth convergent of the continued fraction is expressed as the fraction R/S, then the house number is RS. A little algebra gives the n+1th convergent as (R+2S)/(R+S). Then the house number in the n+1th solution is

    R'S' = (R+2S)(R+S)

    Since R/S converges to 2^(1/2), we can substitute 2^(1/2) S with R to find that R'S' is approximately

    (R + 2^(1/2) R) (2^(1/2) S + S) = (3 + 2^(3/2)) RS

    which agrees with my observation.

  • @Eduardo Quadros, I believe your results can be generalised in a way that makes it clear what the limits are. If we define:

    b(n,m) = sqrt(1 + n sqrt(1 + (n+1) sqrt(1 + … sqrt(1+m))))

    for any positive integer n and any integer m greater than or equal to n, then your series b_m is the particular case b(2,m). And just as you proved that b_m is a monotonically increasing sequence that starts at sqrt(3) and is bounded above by 3, analogous calculations show that, in general, b(n,m) is a monotonically increasing sequence (for m = n,n+1,…) that starts at sqrt(n+1) and is bounded above by n+1.

    Now, we have the recurrence relation for any specific values of n and m:

    b(n,m)^2 = 1 + n b(n+1,m)

    Since we are taking continuous functions of the two series b(n,m) and b(n+1,m), the relationship will also hold in the limit as m goes to infinity, which we will write as B(n):

    B(n)^2 = 1 + n B(n+1)


    B(n+1)= (B(n)^2 – 1) / n

    It's easy to see that this will be satisfied if B(n) = n+1 for all positive integers n, which is the upper bound on each series. But we can also prove that no other set of values for B(n) can work.

    Each B(n) must be greater than 1 (since each series starts at sqrt(1+n)), and at most n+1. Suppose B(n) = (n+1)–d(n), for some positive set of values d(n), which must be less than n. From the recurrence relation for B(n+1), we get:

    d(n+1)/d(n) = (2n+2 – d(n)) / n

    Since d(n) is less than n:

    d(n+1)/d(n) is greater than (n+2)/n


    d(n+2)/d(n+1) is greater than (n+3)/(n+1)
    d(n+3)/d(n+2) is greater than (n+4)/(n+2)
    d(n+4)/d(n+3) is greater than (n+5)/(n+3)

    Multiplying a string of p consecutive ratios together, we get:

    d(n+p)/d(n) is greater than [(n+p)(n+p+1)]/[n(n+1)]

    If we choose p greater than (n+1)(n–d(n)) / d(n), this gives:

    d(n+p) is greater than n+p

    which contradicts the upper bound that must apply to every d.

  • @Greg Egan, That is so much more inventive than my plan of looking for another sequence that bounds b_n from bellow. It was a pleasure to go through your proof. Thank you 😀

  • I'm not sure if anyone has mentioned this yet: the recurrence relation for the house number solutions is

    b_n = 6b_n-1 – b_n-2

    Solving this as a difference equation yields the same closed form solution as before (here stated slightly more elegantly)

    b_n = (K^n – K^(-n)) / (K – K^(-1))

    where K = 3 + 2sqrt(2)

  • We can generalise the infinite nested radical mentioned in prob 1 as

    a =√1+(a-1)√1+a√1+(a+1)√1+(a+2)√1+⋯


  • 2 Greg Egan:

    I'm understend how we get it: 2 H^2 – N(N+1) = 0
    But how you get follow recurrence relation:

    H' = 1+3H+2N
    N' = 1+4H+3N

    Can you explait it in more details, please?

  • @bayah

    If we assume that there is a linear recurrence relation, we can write:

    H' = a H + b N + c
    N' = d H + e N + f

    It makes the algebra a bit simpler if we know the first three solutions: (H,N) = (0,0), (1,1), (6,8). To get from (0,0) to (1,1), clearly you need c=f=1. To get from (1,1) to (6,8) you need a+b+1=6, d+e+1=8. So we can rewrite the recurrence relation as:

    H' = a H + (5–a) N + 1
    N' = d H + (7–d) N + 1

    We want to choose a,d so that:

    2 H'^2 – N'(N'+1) – (2 H^2 – N(N+1)) = 0

    If we substitute the expressions for H' and N' into that equation, setting the coefficients of N and H^2 to zero gives us:

    3d – 4a = 0
    2a^2 – d^2 – 2 = 0

    The only solutions to this are a=3, d=4 and a=–3, d=–4, and it's easy to check that the second solution doesn't work. So b=5–a=2 and e=7–d=3, giving the result:

    H' = 1+3H+2N
    N' = 1+4H+3N

  • @Greg Egan

    After substitute H' and N' we got:
    H^2(2a^2-d^2-2) + NH((5-a)4a-(7-d)2d) + H(4a-3d) + N^2(2(5-a)^2-(7-d)+1) + N(3d-4a) = 0

    But, i can't understand why now we can "setting the coefficients of N and H^2 to zero" ?
    And why for N and H^2? What about others coefficients, for example N^2 or NH?

  • @bayah

    There are only two variables, a and d, so the 5 equations we get from the 5 coefficients can't all be independent. So, we pick any two independent equations and solve them, and then check whether or not the solution they give solves all 5 equations. Having all 5 coefficients equal to zero means the whole expression will be zero, whatever the values of H and N. So:

    2 H'^2 – N'(N'+1) – (2 H^2 – N(N+1)) = 0

    which is a sufficient condition for the recurrence relation to give a solution (H',N') whenever (H,N) is a solution.

    We haven't proved that it's a necessary condition, so if there had been no values of a,b,c,d,e,f that made this true we would have needed to work a bit harder to prove that no such recurrence relation existed.

  • @bayah

    BTW, there is a small mistake in the coefficient you've written for N^2. You've written this as:


    which is equal to 6 for a=3, d=4. The correct coefficient is:

    2(5–a)^2 –(7–d)^2+1

    which is equal to 0 for a=3, d=4.

  • @Greg Egan

    Oh, thx for explanation, now I get it.)
    I just forgot that whole expression equal to zero and therefore coefficients with necessary will be zero too.
    And onother one,…you write:

    "We haven't proved that it's a necessary condition, so if there had been no values of a,b,c,d,e,f that made this true we would have needed to work a bit harder to prove that no such recurrence relation existed."

    How can it be so that coefficients may have no values?
    And in this case, since we do not know whether it is a necessary condition, can this puzzle have another solve?

    P.S. sorry for my English,
    I hope that it will be clear that I wanted to say)

  • @Greg Egan

    I think the latter half of your solution to problem 3 can be much simplifed as follows:

    By the recursive formulas:
    n' = n + d
    d' = d + 2n
    and the initial condition that n=2 and d=3, it can be easily shown that
    d^2 = 2*n^2 + 1 or
    d^2 = 2*n^2 – 1

    for all the convergents of 1/sqrt(2)

    If d^2 = 2*n^2 + 1 , define H = nd , N = 2*n^2
    then 2*H^2 = 2*n^2*d^2 = 2*n^2*(2*n^2 + 1) = N * (N+1)

    If d^2 = 2*n^2 – 1, define H = nd, N = (2*n^2 – 1)
    then 2*H^2 = 2*n^2*d^2 = 2*n^2*(2*n^2-1) = N * (N+1)

    So we have shown that 2*H^2 = N * (N+1) for both cases.

  • (Cont.)

    The converse is also true. That means, if 2*H^2 = N*(N+1), then because N and N+1 must have no common factors (i.e. gcd(N,N+1)=1), there must exist n,d such that

    H = nd
    N = 2*n^2 or N+1 = 2*n^2

    2*n^2*d^2 = 2*n^2*(2*n^2 + 1)
    2*n^2*d^2 = 2*n^2*(2*n^2-1)

    In either case, d^2-2*n^2 = +/-1

    It implies that solving 2*H^2=N*(N+1) is equivalent to solving d^2-2*n^2 = +/-1. The solutions of the latter is completely given by the convergents of continued fraction of sqrt(2) (or 1/sqrt(2), which are just reciprocals).

  • @Eric Wong

    Thanks, that's definitely more concise!


    What we've been able to prove is that, if:

    H' = 1+3H+2N
    N' = 1+4H+3N


    2 H'^2 – N'(N'+1) = 2 H^2 – N(N+1)

    for ALL values of H and N. That is obviously sufficient to imply that if (H,N) is a solution to 2 H^2 – N(N+1) = 0, then so is (H',N'). But it's actually a stronger condition than we need; in principle, we only need it to be true when (H,N) is a solution. The way things turned out, we easily proved the stronger statement, so we have nothing to worry about. I just wanted to be clear that it would take some further arguments to decide whether this stronger statement is necessary as well as sufficient.

    You also ask if there might be other solutions not given by this recurrence relation. I think we can prove that this is impossible by inverting the recurrence relation. We can invert:

    H' = 1+3H+2N
    N' = 1+4H+3N

    to get:

    H = 3H' – 2N' –1
    N = 3N' – 4H' +1

    If there was an extra solution (H*,N*) between two of those given to us by the recurrence relation starting from (0,0), we could apply the inverse recurrence relation to (H*,N*) repeatedly, and eventually it would have to give us a new solution between (0,0) and (1,1), which is impossible.

    That relies on the relation:

    H1 < H2


    H1' < H2'

    when H1' and H2' are linked to H1 and H2 by the recurrence relation, using values N1, N2 that are solutions. That's easy to prove, but I'll leave it as an exercise.

  • @Greg Egan

    Starting with 2 H^2 = N(N+1), I came with the solutions for (H, N) as
    (6, 8), (35,49)… and a different recurrence relation, viz.

    N'' = 6N' – N + 2

    Where, N, N' are two consecutive solutions. (My solution is posted above).
    (It is easy to prove the equivalence of your recurrence relation with mine)

    However, I could not prove that these are the only solutions.
    From your recurrence relation, it is easy to prove that those are the only solutions.

  • I saw the mistake in my answer 3, in the sequence of numbers 1 to 13 the number is not 9. So the general rule i used is also wrong.

  • @Greg Egan

    I don't fully realize and so I ask two specifying question.

    First. You write that we prove that our recurrence relation get solution for ALL values of H and N. So if the solution giving by this recurrence relation get ALL possible and there is no other solution, does it means that recurrence relation is a neccessary condition?

    And so, second question. If one recurrence relation giving solution that responded our condition 2H'^2 – N'(N'+1) = 2H^2 – N(N+1) = 0, how we can be sure that is ALL solution? For example, may be our solution gives first, second, fourth, … solution missing third.

  • @bayah

    1. Now that we have proved that the recurrence relation gives all solutions, then two consecutive solutions must satisfy it, so we've proved that's it's a necessary condition for two solutions being consecutive ones.

    2. We could easily write a new recurrence relation that only gave us every second solution, just by repeating the original relation. The result is:

    H' = 6 + 17 H + 12 N
    N' = 8 + 24 H + 17 N

    This also satisfies:

    2H'^2 – N'(N'+1) = 2H^2 – N(N+1)

    for any value of H, N. But because we know that the first two solutions are (0,0) and (1,1), we can immediately see that this misses at least one solution, and with a little more work see that it gives us exactly every second solution.

  • @Greg Egan

    2. But because we know that the first two solutions are (0,0) and (1,1), we can immediately see that this misses at least one solution, and with a little more work see that it gives us exactly every second solution.

    Yes, in this case we can realize that new recurrence relation missed solution, but it's just because we know first solution directly. What if missed solution located far on natural number axis? Sure, in this case, we can slill notice that new recurrence relation gives less solutions than the original relation. But, how can we know, that the original relation does not missed any solution at infinity? In this case, we do not have the other recurrence relation which could be compared to the original.

  • @bayah

    As I explained earlier, if there was a "missed solution" (H*,N*) anywhere at all that was positioned between two consecutive solutions generated by the original recurrence relation, then repeatedly applying the inverse recurrence relation to (H*,N*) would eventually produce an extra solution between (0,0) and (1,1), which is impossible.

  • It is interesting to look at generalisations of these problems, as well as the problems themselves.

    1. Let f_0, f_1, f_2, … be a sequence of positive numbers satisfying the nonlinear recurrence relation
    (f_n)^2 = a + b f_{n-1} f_{n+1}.
    For example,
    f_n = n+x (*)
    is a solution for the case a=b=1, for any positive real number x. A second example of interest I have found is
    f_n = cosh nx, (**)
    for the case a = – (sinh x)^2 and b=1.

    Repeated application of the recurrence relation gives the exact result
    f_1 = \sqrt{a + bf_0 \sqrt{a + bf_1 \sqrt{ a + …. + bf_N f_{N+2}…}} (***)
    for any integer N>0. In the given problem, one has a=b=1 and f_n=n+2, and letting N become arbitrarily large gives the desired answer. Choosing x>0 to be something other than 2 in Eq. (*), e.g., x=1/2, gives a similar series for any value f_1=1+x.

    However, while the formula in Eq. (***) is correct for any finite N, it does not really make sense to take the limit N –> infinity, as the terms just get larger and larger. This is most easily seen for the solution in Eq. (**), which gives the correct formula
    cosh x = \sqrt{-(sinh^2 x + \sqrt{-sinh^2 x + cosh x \sqrt{ -sinh^2 x + ….
    …….+ cosh Nx cosh (N+2)x … } }
    for any finite N. It is seen that if one takes N arbitrarily large and ignores the final term then one is taking square roots of negative numbers at every stage.

    2. This problem is well known: the golden mean is the most slowly converging continued fraction. I have seen a generalisation to the (positive) continued fraction
    x = 1/(n + 1/(n + …..
    for positive integers n, where n=1 is the golden mean, n=2 can be called the silver mean, etc. In this case 1/x – n = x, giving the quadratic equation
    x^2 + nx – 1 = 0,
    which has the positive root
    x = (1/2) [ \sqrt{ n^2 + 4 } – n ].
    As n–>infinity, this converges to 1/n –> 0, as one expects from the definition of x.

    3. If the house number is n and the number of houses is N, then
    T_{n-1} = 1+2+..+ (n-1) = (n+1) + (n+2) +…+ N = T_N – T_n,
    where T_n denotes the sum of the first n integers. Using T_n = (1/2)n(n+1) then gives
    T_N = (1/2) N(N+1) = n^2. (*)

    For large N the left hand side is ~(1/2)N^2 (corresponding geometrically to the area of the triangle
    * *
    * * *
    etc, for the triangular number T_N), and so one has
    n/N ~ 1/\sqrt{2}, (**)
    accurate to less than 1/N. No doubt Ramanujan simply evaluated the continued fraction of 1/\sqrt{2}, with each truncation corresponding to a solution (he certainly didn't work out several small value solutions and then estimate a continued fraction from these). I haven't tried learning enough about continued fractions to work out 1/sqrt{2}, however.

    Note that this is NOT the same as evaluating the continued fraction of \sqrt{2}. One can get some insight into why by multiplying Eq. (*) by 4 and rearranging, to give
    (2N+1)^2 – 2 (2n)^2 = 1.
    This is a special case of the Pell equation, x^2 – r y^2 = 1, for r=2, with integer solutions for x and y given by successive terms of the continued fraction for \sqrt{r} (according to Wikipedia). However, in our case, we have the further constraint that
    x = 2N+1 = odd, and y = 2n =even, which is only satisfied by every SECOND fraction generated by the continued fraction
    \sqrt{2} = 1 + 1/(2 + 1/(2 + 1/……. .
    These 'every second' fractions are 1, 3/2, 17/12, …, corresponding to
    (n,N) = (1,1), (6, 8), ….

    Actually, it doesn't seem very impressive to give the set of all possible solutions in terms of a continued fraction: actually finding the explicit analytic form seems nicer to me — although perhaps not to someone like Ramanujan, who could think in terms of continued fractions!

    I see @Tom Nicols has given an exact form, based on numerical induction. It is interesting to note that his solution corresponds to the recurrence relation
    f_{n+1} = 6 f_{n+1} – 1,
    which has the general solution of the form
    f_n = A K^n + B (1/K)^n
    for constants A and B and K=3+sqrt{8}. As he notes, this means one can write the possible house numbers in the simple form
    solution_n = round{AK^n}.
    I understand that quadratic irrationals, like 1/sqrt{2}, have repeating continued fraction expansions specifed by a quadratic equation — in this case, one therefore suspects that the quadratic equation is
    x^2 = 6x – 1.

  • Oops, in the very last paragraph of my previous comment, the stated recurrence relation
    f_{n+1} = 6 f_{n+1} – 1
    was meant to have been
    f_{n+1} = 6 f_n – f_{n-1}.

  • "What if Ramanujan had modern calculating tools?"

    He would have never developed the intuitions about numbers that he had.

    Calculation of phi:

    Speaking of modern calculators, it is very easy to use the continued fraction to calculate phi:

    Start with 1
    add 1
    divide that sum into 1
    add 1
    divide into 1
    repeat the last two steps n times.

    when you get bored divide the last number into 1

    The calculated result will converge on phi with great rapidity.

    The key stokes on my HP calculator are:

    1 [enter]
    1 +
    1 +
    n times

  • I see that the above description was a bit ambiguous. I hope this is better:

    The key stokes [ ] on my HP calculator are:

    1 [enter]
    1 [+]
    Repeat the following n times:
    1 [+]
    After n repetitions:

  • Looking at it again, I remember that the last step can also be:


    The result is the same (1/phi) + 1 = phi

  • Ramanujan discovered a general formula that produced another equation for the golden ratio, an infinite product series.
    The expression relates three important numbers of math–epsilon, pi, and phi (the golden ratio)–such that the logarithmic spiral (e^pi), when offset by the series expansion, produces the golden ratio at pi/6 intervals.

    Here is a link showing the equation if anyone is interested:

    …and here is a link to the blog discussing Ramanujan's general formula:

  • Gotthold Eisenstein is another mathematician that you might mention has having died so young, at age 29. He was jailed for political reasons and got sick.

  • @Greg Egan:
    But for what we repeatedly applying the inverse recurrence relation to (H*,N*)? It's inverse recurrence original recurrence. What we want to get applying it to the solution, that do not given by our suggestion.

    And why by this way we neccessary produce solution between (0,0) and (1,1)?

  • @bayah

    I've already explained this in the earlier comment:

    If you don't understand what I've written there, I'm sorry, I can't help you.

  • Looking again at finding the explicit analytic solutions, as found numerically for the house number by @Tom Nichols, they turn out to be
    Number of the house:
    n_r = (K^r – 1/K^r) / (2 sqrt(2) ) = trunc[ K^r / (2 sqrt(2)) ]
    Number of houses in the street:
    N_r = (K^r + 1/K^r) / 4 -1/2 = trunc[ K^r /3 ],
    where K = 3 + sqrt{2} (implying that 1/K = 3 – sqrt(2).
    The first solutions are
    (n,N) = (0,0), (1,1), (6,8), …
    corresponding to r=0,1,2,…

    It is interesting to note that the total number of houses can also be written as
    N_r = (L_r)^2 = 2 ( n_{r/2} )^2 ,
    extending r to arbitrary numbers, with
    L_r := (K^{r/2} – 1/K^{r/2}) / 2 = sqrt(2) n_{r/2}.

    The explicit form comes from writing the solution (n,N) using the continued fraction for 1/sqrt{2}, as per my first post, where every second term of the continued fraction is of the form (2n)/(2N+1). This gives a recurrrence relation which can then be solved. In particular, noting that the continued fraction for sqrt{2}-1 is the "silver mean"
    x = 1/(2 + 1/(2 + 1/(2 +….. ,
    then substituting x_r = a_r/b_r for the r'th odd term gives
    x_{r+1} = 1/(2 + 1/(2 + x_r) = (a_r+2b_r)/(2a)r+5b_r),
    which, since 1/sqrt{2} = 1/(1+x), yields the required successive values of (2n_r)/(2N_r+1) = p_r/q_r (*)
    as the recurrence relation
    p_{r+1}/q_{r+1} = (3p_r+2q_r) / (4p_r + 3q_r).
    This may be put in the "matrix" form:
    (p_{r+1}) = (3 2) (p_r)
    (q_{r+1}) (4 3) (q_r).
    The general solution for p_r and q_r is thus found by applying the matrix
    M = (3 2)
    (4 3)
    to the initial vector (p_0 q_0). Since the eigenvalues of M are found to be K and K^{-1} (where the eigenvalue equation is z^2-6x+1 as suggested in my previous post), then using the Jordan canonical representation for M and Eq. (*) above for n_r and N_r in terms of p_r and q_r gives the general form
    n_r = A K^r + B/K^r,
    N_r = C K^r + D/K^r – 1/2
    for suitable constants A, B, C and D. These may be found from the first couple of continued fraction results, leading to the solution given at the top of this post.

  • I see I mistyped the second form of my general solution for the total number of houses N_r: it should of course have been
    trunc[ K^r / 4 ],
    as follows from the first form. Pity that the matrices don't format properly.

  • I'm not a mathematician but playing with the fun little infinite
    division that comes from (x+1)^2 there are obvious infinite divisions
    for all numbers 4, 5, 6…

    Also I looked at (x+1)^3 and found a cubic root infinite equation that's
    a bit more complicated but has the same kind of repetition. I'd think
    there's infinite divisions for all the powers and the formula is
    related to the binomial coefficients. So each integer can be
    expressed as infinite divisions of sqrts, infinite divisions of cubic
    roots, infinite divisions of quadratic roots, etc….. how to express
    that is beyond me. True?

Comments are closed.