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

Given a large number, n, find all positive numbers less than or equal to n that can be represented as the sum of two cubes for at least two different pairs.

In other words, find all positive numbers m <= n that can be expressed as:

m = (a³ + b³) = (c³ + d³) 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 the sum of two cubes for two different pairs.

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

Practice this problem

The idea is simple. We know that any number m that satisfies the constraint will have two distinct pairs (let's say (a, b) and (c, d)). Since m < n, we can say that a, b, c, and d are less than n^1/3. Now for every distinct pair (x, y) formed by numbers less than the n^1/3, store their sum x³ + y³ into a set. If two pairs with the same sum exist, print the sum.

Following is the C++, Java, and Python implementation of the idea:

C++

#include <iostream>

#include <unordered_set>

#include <cmath>

using namespace std;

void findAllNumbers(int n)

{

// find the cube root of `n`

int cb = pow(n, 1.0 / 3);

// create an empty set

unordered_set<int> s;

for (int i = 1; i < cb - 1; i++)

{

for (int j = i + 1; j < cb + 1; j++)

{

// (i, j) forms a pair

int sum = (i*i*i) + (j*j*j);

// sum is seen before

if (s.find(sum) != s.end()) {

if (sum <= n) {

cout << sum << endl;

}

else {

// sum is not seen before

s.insert(sum);

}

int main()

{

int n = 25000;

findAllNumbers(n);

return 0;

}

Download Run Code

Output:

1729
4104
13832
20683

Java

import java.util.HashSet;

import java.util.Set;

class Main

{

public static void findAllNumbers(int n)

{

// find the cube root of `n`

int cb = (int)Math.pow(n, 1.0 / 3);

// create an empty set

Set<Integer> s = new HashSet<>();

for (int i = 1; i < cb - 1; i++)

{

for (int j = i + 1; j < cb + 1; j++)

{

// (i, j) forms a pair

int sum = (i*i*i) + (j*j*j);

// sum is seen before

if (s.contains(sum)) {

if (sum <= n) {

System.out.println(sum);

}

else {

// sum is not seen before

s.add(sum);

}

public static void main(String[] args)

{

int n = 25000;

findAllNumbers(n);

}

Download Run Code

Output:

1729
4104
13832
20683

Python

def findAllNumbers(n):

# find the cube root of `n`

cb = int(pow(n, 1.0 / 3))

# create an empty set

s = set()

for i in range(1, cb - 1):

for j in range(i + 1, cb + 1):

# (i, j) forms a pair

sum = (i*i*i) + (j*j*j)

# sum is seen before

if sum in s:

if sum <= n:

print(sum)

else:

# sum is not seen before

s.add(sum)

if __name__ == '__main__':

n = 25000

findAllNumbers(n)

Download Run Code

Output:

1729
4104
13832
20683

The time complexity of the above solution is O(n^2/3).