How to find all taxicab numbers less than N?

Question

A taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: a^3+b^3 = c^3+d^3. Design an algorithm to find all taxicab numbers with a, b, c, and d less than N.

Please give both the space and time complexity in terms of N. I could do it in o(N^2.logN) time with O(N^2) space.

Best algorithm I've found so far:

Form all pairs: N^2
Sort the sum: N^2 logN
Find duplicates less than N

But this takes N^2 space. Can we do better?

Answer 1

But this takes N^2 space. Can we do better?

There exists an O(N) space solution based on a priority queue. Time complexity is O(N^2 logN). To sketch out the idea of the algorithm, here is the matrix M such that M[i][j] = i^3 + j^3 (of course, the matrix is never created in memory):

0    1    8    27    64    125 1    2    9    28    65    126 8    9    16   35    72    133 27   28   35   54    91    152 64   65   72   91    128   189 125  126  133  152   189   250 

Observe that every line and every row is sorted in ascending order. Let PQ be the priority queue. First we put the biggest element in the priority queue. Then perform the following, as long as the PQ is not empty:

1. Pop the biggest element from PQ
2. add adjacent element above if the PQ doesn't have any element from that row
3. add adjacent element on the left if the PQ doesn't have any element from that column, and if it is not under the diagonal of the matrix (to avoid redundant elements)

Note that

1. You don't need to create the matrix in memory to implement the algorithm
2. The elements will be popped from the PQ in descending order, from the biggest element of the matrix to its smallest one (avoiding elements from the redundant half part of the matrix).

Everytime the PQ issues the same value twice then we have found a taxicab number.

As an illustration, here is an implementation in C++. The time complexity is O(N^2 logN) and space complexity O(N).

#include <iostream> #include <cassert> #include <queue>  using namespace std;  typedef unsigned int value_type;  struct Square {     value_type i;     value_type j;     value_type sum_of_cubes;     Square(value_type i, value_type j) : i(i), j(j), sum_of_cubes(i*i*i+j*j*j) {}     friend class SquareCompare;     bool taxicab(const Square& sq) const     {         return sum_of_cubes == sq.sum_of_cubes && i != sq.i && i != sq.j;     }     friend ostream& operator<<(ostream& os, const Square& sq); };  class SquareCompare { public:     bool operator()(const Square& a, const Square& b)     {     return a.sum_of_cubes < b.sum_of_cubes;     } };  ostream& operator<<(ostream& os, const Square& sq) {     return os << sq.i << "^3 + " << sq.j << "^3 = " << sq.sum_of_cubes; }  int main() {     const value_type N=2001;     value_type count = 0;     bool in_i [N];     bool in_j [N];      for (value_type i=0; i<N; i++) {     in_i[i] = false;     in_j[i] = false;     }      priority_queue<Square, vector<Square>, SquareCompare> p_queue;      p_queue.push(Square(N-1, N-1));     in_i[N-1] = true;     in_j[N-1] = true;      while(!p_queue.empty()) {     Square sq = p_queue.top();      p_queue.pop();     in_i[sq.i] = false;     in_j[sq.j] = false;      // cout << "pop " << sq.i << " " << sq.j << endl;      if (sq.i > 0 && !in_i[sq.i - 1] && sq.i-1 >= sq.j) {         p_queue.push(Square(sq.i-1, sq.j));         in_i[sq.i-1] = true;         in_j[sq.j] = true;         // cout << "push " << sq.i-1 << " " << sq.j << endl;     }     if (sq.j > 0 && !in_j[sq.j-1] && sq.i >= sq.j - 1) {         p_queue.push(Square(sq.i, sq.j-1));         in_i[sq.i] = true;         in_j[sq.j - 1] = true;         // cout << "push " << sq.i << " " << sq.j-1 << endl;     }      if (sq.taxicab(p_queue.top())) {         /* taxicab number */         cout << sq << " " << p_queue.top() << endl;         count++;     }     }     cout << endl;      cout << "there are " << count << " taxicab numbers with a, b, c, d < " << N << endl;      return 0; }