Introduction

In mathematics, a taxicab number or Hardy–Ramanujan number is the smallest number that can be expressed as a sum of two positive cubes in n different ways. The name originates from a famous anecdote involving mathematicians G.H. Hardy and Srinivasa Ramanujan regarding the number 1729, which is the smallest number that can be expressed as the sum of two cubes in two different ways:

$$1729 = 1^3 + 12^3 = 9^3 + 10^3$$

This article delves into finding all taxicab numbers less than a given number N , exploring algorithms and methods, while providing examples and a summary table.

Problem Definition

Given a number N , our objective is to identify all taxicab numbers less than N . The basic requirement is to compute sums of two different cubes in multiple ways and identify the smallest number which satisfies this condition for various (a, b) pairs where a and b are positive integers.

Algorithm Approach

To find the taxicab numbers, we can leverage brute force computations or more optimized approaches using computational geometry or advanced data structures. Below, we discuss a more systematic algorithmic method:

Algorithm Steps

1. Initialize a Limit: Since max(a^3, b^3) must be less than N , compute L = N^\{1/3\} to set upper bounds for a and b .
2. Utilize a Map Data Structure: Use a dictionary (or a hashmap) to track integer sums. Keys represent the sum x = a^3 + b^3 , and associated values are lists of pairs (a, b) that generate the key sum.
3. Iterate Over Potential Cubes:
   • Loop over a and b such that $1 \leq a, b \leq L$.
   • Calculate s = a^3 + b^3 .
   • If s < N , check if s is present in the map:
     • If present, append the pair (a, b) to the list associated with s .
     • If not, initiate a new list with (a, b) .
4. Extract Taxicab Numbers: Traverse the map and identify numbers that can be formed in multiple ways. This means having more than one pair (a, b) for x .

Here's a sketch in Python for clarity:

• 1729: represented as $1^3 + 12^3$ and $9^3 + 10^3$.
• Optimization: Although the approach loops over a and b quadratically, it can be optimized using symmetry since $a^3 + b^3 = b^3 + a^3$. Hence, only pairs where a <= b need to be computed.
• **Large N **: When N is significantly large, computational methods such as parallel processing or using GPUs can be employed to speed up cube sum calculations.