I think it was the year 1986 when I participated in an interschool programming competition in Chennai. I wasn’t very good at math, but I did tag along with a couple of my friends who were darn good at it. There were three problems given that we have to solve using GW-BASIC in about 30 minutes. There were probably 100 participants. I did get a peep into a few poor guys inside the computer room who were typing our solutions into the computer blindly and see if they worked. I just remember only one of the problems. I didn’t get the correct solution, but one of my friends – Sowmy Srinivasan, did and win the competition.
Years later, I learned that this was a very interesting puzzle tackled by the genius Srinivasa Ramanujan. In the year 1914, PC Mahalanobis, a Kings college student in England, got hold of a puzzle from the Strand magazine.
“In a given street of houses with consecutive numbers between 50 and 500, find the house number, for which, the sum of numbers on the left is equal to the sum of numbers on the right”
In other words, given ‘n’ number of houses, find the house number ‘m’ that would sum(1..m-1) = sum(m+1..n).
Mahalanobis solved the problem by trial and error and went to Ramanujan to show it. Ramanujan was cooking some vegetables in the pan. The instant he heard the problem, Ramanujan, while still frying his veggies, not only gave the answer to the puzzle, but also provided the generic formula that would give infinite number of solutions. The problem belongs to the area called Continuous Fractions and is very fascinating. The problem can be reduced to x*x – Dy*y = ±1 and has been tackled by ~10th century Indian mathematician Brahmaguputa using a method called chakravala. I will probably write up on the “chakravala” method later. The Ramanujan anecdote is documented in several places on the net and a simple search will provide more interesting details.
So I was working on something in Groovy, I suddenly got reminded of this problem and was thinking if this can be solved as a Groovy OLC. I am going to use the brute-force method rather than solving via the quadratic equation, because it nicely demostrates the List capabilities of Groovy. It does run slow for large numbers, but speed or optimization is not the point here.
So here is Groovy OLC #2 – Ramanujan’s Continuous Fractions (via brute force method)
public test_ramanujan_continous_fraction() {
(1..100).each { n, houses = 1..n -> houses.eachWithIndex {m, i -> if (houses.subList(0,i).sum() == houses.subList(i+1,houses.size()).sum()) println "house# = $m, total_houses = $n" } }
}
Result:
house# = 1, total_houses = 1
house# = 6, total_houses = 8
house# = 35, total_houses = 49
Ignore the first one, as I am not bothered about boundary conditions, though its technically correct.
[6,8] = sum(1..5) = sum(7..8) = 15
[35,49] = sum(1..34) = sum(36..49) = 595
Lets retest it with the actual problem from the Strand magazine:
public test_ramanujan_continous_fraction() {
(50..500).each { n, houses = 1..n -> houses.eachWithIndex {m, i -> if (houses.subList(0,i).sum() == houses.subList(i+1,houses.size()).sum()) println "house# = $m, total_houses = $n" } }
}
Result:
house# = 204, total_houses = 288
This is the actual solution that Ramunjan gave instantly to the Strand’s puzzle.
From Groovy’s point of view, the most interesting thing is the second argument in the first closure – “houses” – is actually a variable defintion which is a function of the first argument, ie houses = f(n) !!!
Vasya's Weblog 