Click here to Skip to main content
15,867,835 members
Please Sign up or sign in to vote.
2.00/5 (8 votes)
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.

[edit]
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.

[edit]
Posted
Updated 26-Jul-12 0:47am
v3
Comments
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.

1 solution

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.
 
Share this answer
 
Comments
Richard MacCutchan 27-Jul-12 5:32am    
Good answer +5
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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900