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

I make on python which print slighter more solution than the previous solution, idk if it can be optimized further i add some comment to help explain

find all positive integer solutions under 1,000 to a3 + b3 = c3 + d3 (a+b)(a2-ab+b2) = (c+d)(c2-cd+d2);

enter code here

#find all positive integer solutions under 1,000 to a3 + b3 = c3 + d3 
# (a+b)(a2-ab+b2) = (c+d)(c2-cd+d2);
n = 1000
dict1={}


solution = []
solution_visual =[]
k=0
#cycle for finding the cube sums of pairs c and d 
for c in range(n):
 for d in range(n):
  result = (c**3) + (d**3)
  if result not in dict1:
    dict1[result] =(c,d)
  else:
    list = dict1[result]
  #check that the numbers of the quadruplet are unique
  if (list[0]!=list[1] and list[0]!=c and list[0]!=d and list[1]!=c 
   and list[1]!=d and c!=d):
    tuple1 = (list[0],list[1],c,d) 
    #check that the two pairs are unique (we exclude the same number with different order)
    srtd_tp=sorted(tuple1)
    srtd_tp = tuple(srtd_tp)
    #add to the final list only if they are not there before
    if srtd_tp not in solution:
     solution.append(srtd_tp)
     solution_visual.append(tuple1) #we visualize them in the correct 
     order.
     k+=1 #keep the count of the solutions
#sorting the solutions to better visualize
solution.sort()
solution_visual.sort()

#print the solutions quadruplets 
for tuple in solution_visual:
  print(tuple)

Answer 2

@Dmitry's answer is a good first step, but is missing a couple of scenarios. @pau mentioned one scenario where a == b - those should be included even though they will only be counted once during the iterations.

Also, the second loop needs to reset the variable b to 1, not a. Otherwise, you do not capture the combinations of (1,2) = (2,1).

UPDATE: You could keep the second loop as-is and just make sure to automatically include the reciprocal of (a,b). So in essence, every (a,b) pair should automatically be included since it's reciprocal pair, (b,a), will equate.

Answer 3

We could achieve even a simpler solution computing all different options for "a" and "b", then adding those into a Dictionary<int, List<Tuple<int,int>>> as @Dimitry states, but, then changing the report generation to:

foreach (List<Tuple<int,int>> l in solutions.Values) {
  foreach(Tuple<int,int> t1 in  l) {
    foreach(Tuple<int,int> t2 in l) {
       Console.Write("({0},{1})({2},{3})", t1.Item1, t1.Item2, t2.Item1, t2.Item2);
    }
  }
}

There's no need of checking whether one of the solutions contains more than 1 Tuple in the List. Single Tuple Lists are also valid solutions since any (a,b) values can also be represented by (c,d) making c = a and d = b, therefore those should be included in the report as well.

This way, you also solve the inconsistency noticed by @Dimitry of having a solution with triple representations.

Answer 4

To restate @Dmitry's answer (who should get all the credit) in pure LINQ:

from a in Enumerable.Range(1, 1000)
from b in Enumerable.Range(a, 1000 - a + 1)
let sum = a * a * a + b * b * b
group $"{a}^3 + {b}^3" by sum into g
where g.Count() > 1
orderby g.Key   // just for niceness
select $"{g.Key} = " + String.Join(" = ", g)

Answer 5

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)