``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 ``` ```package algs24; import stdlib.*; /* *********************************************************************** * Compilation: javac Taxicab.java * Execution: java Taxicab N * * Find all nontrivial integer solutions to a^3 + b^3 = c^3 + d^3 where * a, b, c, and d are between 0 and N. By nontrivial, we mean * a <= b, c <= d, and (a, b) != (c, d). * * % java Taxicab 11 * * % java Taxicab 12 * 1729: 9^3 + 10^3 * 1729: 1^3 + 12^3 * * % java Taxicab 1000 * 1729: 1^3 + 12^3 * 1729: 9^3 + 10^3 * 4104: 2^3 + 16^3 * 4104: 9^3 + 15^3 * 13832: 2^3 + 24^3 * 13832: 18^3 + 20^3 * ... * 87539319: 228^3 + 423^3 * 87539319: 167^3 + 436^3 * 87539319: 167^3 + 436^3 * 87539319: 255^3 + 414^3 * ... * 1477354411: 802^3 + 987^3 * 1477354411: 883^3 + 924^3 * *************************************************************************/ public class XTaxicab implements Comparable { private final long sum; private final int i; private final int j; // create a new tuple (i, j, i^3 + j^3) public XTaxicab(int i, int j) { this.sum = (long) i*i*i + (long) j*j*j; this.i = i; this.j = j; } public int compareTo(XTaxicab that) { if (this.sum < that.sum) return -1; else if (this.sum > that.sum) return +1; else 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 pq = new MinPQ<>(); for (int i = 1; i <= N; i++) { pq.insert(new XTaxicab(i, i)); } // enumerate sums in ascending order, look for repeated sums XTaxicab prev = new XTaxicab(0, 0); // sentinel while (!pq.isEmpty()) { XTaxicab s = pq.delMin(); // sum is same as previous one if (prev.sum == s.sum) { StdOut.println(prev); StdOut.println(s); } prev = s; if (s.j < N) pq.insert(new XTaxicab(s.i, s.j + 1)); } } } ```