How to find all positive integer solutions to an cubic equation?

Question

I would like to find all positive integer solutions to the equation a^3 + b^3 = c^3 + d^3 where a, b, c, d are integers between 1 to 1000

Brute force solution keep on computing all (c, d) pairs for each (a,b) pair. I want to improve this algorithm. I want to just create the list of (c,d) pairs once. Then, when we have an (a,b) pair, find the matches within (c,d) list. We can quickly locate the matches by inserting each (c,d) pair into a hash table that maps from the sum to the pair (or, rather the list of pairs that have that sum)

n= 1000
for c from 1 to n
    for d from 1 to n
        result = c^3 + d^3
        append (c,d) to list at value map[result]

for a from 1 to n
    for b from 1 to n
        result = a^3 + b^3
        list = map.get(result)
        foreach pair in list
             print a,b, pair

Am I right that we have O(n^2) solution? Why? How can we improve it? What is the c# implementation?

Also, maybe once we have the map of all the (c,d) pairs, we can just use that directly. We don't need to generate the (a,b) pairs. Each (a,b) will already be in map. How to implement this idea?

Answer 1

You can group by all the possible sums and print out groups which contain more than one item. This is O(N**2) algorithm:

  // key is sum and value is a list of representations
  Dictionary<int, List<Tuple<int, int>>> solutions = 
    new Dictionary<int, List<Tuple<int, int>>>();

  for (int a = 1; a <= 1000; ++a)
    for (int b = a; b <= 1000; ++b) {
      int sum = a * a * a + b * b * b;

      List<Tuple<int, int>> list = null;

      if (!solutions.TryGetValue(sum, out list)) {
        list = new List<Tuple<int, int>>();

        solutions.Add(sum, list);
      }

      list.Add(new Tuple<int, int>(a, b));
    }

  String report = String.Join(Environment.NewLine,
    solutions.Values
    .Where(list => list.Count > 1) // more than one item
    .Select(list => String.Join(", ", 
      list.Select(item => String.Format("({0}, {1})", item.Item1, item.Item2)))));

  Console.Write(report);

The output (1585 lines) is

(1, 12), (9, 10)
(1, 103), (64, 94)
(1, 150), (73, 144)
(1, 249), (135, 235)
(1, 495), (334, 438)
...
(11, 493), (90, 492), (346, 428) // <- notice three representations of the same sum
...
(663, 858), (719, 820)
(669, 978), (821, 880)
(692, 942), (720, 926)
(718, 920), (816, 846)
(792, 901), (829, 870)

So we have

   1**3 + 12**3 == 9**3 + 10**3
   ...
   11**3 + 493**3 == 90**3 + 492**3 == 346**3 + 428**3   
   ...
   792**3 + 901**3 == 829**3 + 870**3 

It may be interesting that we have 8 triple representations:

(11, 493), (90, 492), (346, 428)
(15, 930), (198, 927), (295, 920)
(22, 986), (180, 984), (692, 856)
(70, 560), (198, 552), (315, 525)
(111, 522), (359, 460), (408, 423)
(167, 436), (228, 423), (255, 414)
(300, 670), (339, 661), (510, 580)
(334, 872), (456, 846), (510, 828)