15,878,543 members
See more:
Computational number theory.

Write a program CubeSum.java that prints out all integers of the form a3 + b3 where a and b are integers between 0 and N in sorted order, without using excessive space.

That is, instead of computing an array of the N2 sums and sorting them, build a minimum-oriented priority queue, initially containing (03, 0, 0), (13, 1, 0), (23, 2, 0), ..., (N3, N, 0).

Then, while the priority queue is nonempty, remove the smallest item (i3 + j3, i, j), print it, and then, if j < N, insert the item (i3 + (j+1)3, i, j+1). Use this program to find all distinct integers a, b, c, and d between 0 and 10^6 such that a3 + b3 = c3 + d3, e.g., 1729 = 9^3 + 10^3 = 1^3 + 12^3.

Update from user:
C#
```public class CubeSum implements Comparable<CubeSum> {
private final int sum;
private final int i;
private final int j;

public CubeSum(int i, int j) {
this.sum = i*i*i + j*j*j;
this.i = i;
this.j = j;
}

public int compareTo(CubeSum that) {
if (this.sum < that.sum) return -1;
if (this.sum < that.sum) return +1;
return 0;
}

public String toString() {
return sum + " = " + i + "^3" + " + " + j + "^3";
}

public static void main(String[] args) {

int N = Integer.parseInt(args[0]);

// initialize priority queue
MinPQ<CubeSum> pq = new MinPQ<CubeSum>();
for (int i = 0; i <= N; i++) {
pq.insert(new CubeSum(i, i));
}

// find smallest sum, print it out, and update
while (!pq.isEmpty()) {
CubeSum s = pq.delMin();
StdOut.println(s);
if (s.j < N) pq.insert(new CubeSum(s.i, s.j + 1));
}
}

}```

Iam now confused on how to use this program to find all distinct integers a, b, c, and d between 0 and 10^6 such that a3 + b3 = c3 + d3, e.g., 1729 = 9^3 + 10^3 = 1^3 + 12^3.

Posted
Updated 26-Jul-12 0:47am
v3
Joan M 26-Jul-12 5:15am
This is homework... we don't do that... if you have a specific doubt come back.
Richard MacCutchan 26-Jul-12 11:54am
Forget programming for a while and look at the mathematics of the problem. If you do not understand that, and cannot figure out the solution as a mathematical algorithm, then no amount of coding will solve it for you.

Solution 5

If I get things right the output is sorted on the result a pow 3 + b pow 3.
That means that if there are two rows with the same result, they will be placed right after eachother. The first row would give you a and b, the second row would give you c and d.
So suppose you never remove elements from the list, you would simply have to traverse the list once to check for two consequetive rows containing the same result.
Now because you are in fact removing elements it is a bit more complicated than that.
You build the list, like you do in your for next.
Then you scan the list for consequetive rows containing the same result.
This way you have a small part of the results.
Then you start adding elements, but as you add elements, you need to take the return value of insert to get yourself an iterator pointing to the position where it got inserted. If pq does not support that you have to find a way to do that yourself. Then if you have that iterator you check the value of the element before it. If the result is the same you have a hit, next you check the value of the element after it. If it is the same you have another hit.

I did not foresee any code here, since it is homework.

Richard MacCutchan 27-Jul-12 5:32am
BillW33 27-Jul-12 8:47am
Good explanation, helpful without actually writing the code for the OP. +5
pasztorpisti 29-Jul-12 13:23pm
5ed a maximum help I would give on the subject