Find numbers represented as sum of two cubes for two different pairs

Given a large number N, find all positive numbers less than N that can be represented as sum of two cubes for at-least two different pairs.

 

In other words, find all positive numbers M less than given number N that can be expressed as
M = (a^3 + b^3) = (c^3 + d^3) for distinct a, b, c, d.

For example, if N = 25000, M can be any of 1729, 4104, 13832 or 20683 as these numbers can be represented as sum of two cubes for two different pairs.


1729 = 1^3 + 12^3 = 9^3 + 10^3
4104 = 2^3 + 16^3 = 9^3 + 15^3
13832 = 2^3 + 24^3 = 18^3 + 20^3
20683 = 10^3 + 27^3 = 19^3 + 24^3


The idea is very simple and effective. We know that any number M that satisfies the constraint will have two distinct pairs (lets say (a, b) and (c, d)). If we observe, since M < N, we can say that a, b, c and d are less than N1/3. Now for every distinct pair (x, y) formed by numbers less than the N1/3, we store their sum (x3 + y3) in a set. If two pairs with same sum exists, we simply print the sum.

 
C++ implementation –
 

Download   Run Code

Output:

1729
4104
13832
20683

 
Time Complexity of above solution is O(n2/3).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂