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++

Download   Run Code

Output:

1729
4104
13832
20683

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of