001package algs24;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Taxicab.java
005 *  Execution:    java Taxicab N
006 *
007 *  Find all nontrivial integer solutions to a^3 + b^3 = c^3 + d^3 where
008 *  a, b, c, and d are between 0 and N. By nontrivial, we mean
009 *  a <= b, c <= d, and (a, b) != (c, d).
010 *
011 *  % java Taxicab 11
012 *
013 *  % java Taxicab 12
014 *  1729: 9^3 + 10^3
015 *  1729: 1^3 +  12^3
016 *
017 *  % java Taxicab 1000
018 *  1729: 1^3 + 12^3
019 *  1729: 9^3 + 10^3
020 *  4104: 2^3 + 16^3
021 *  4104: 9^3 + 15^3
022 *  13832: 2^3 + 24^3
023 *  13832: 18^3 + 20^3
024 *  ...
025 *  87539319: 228^3 + 423^3
026 *  87539319: 167^3 + 436^3
027 *  87539319: 167^3 + 436^3
028 *  87539319: 255^3 + 414^3
029 *  ...
030 *  1477354411: 802^3 + 987^3
031 *  1477354411: 883^3 + 924^3
032 *
033 *************************************************************************/
034
035public class XTaxicab implements Comparable<XTaxicab> {
036        private final long sum;
037        private final int i;
038        private final int j;
039
040        // create a new tuple (i, j, i^3 + j^3)
041        public XTaxicab(int i, int j) {
042                this.sum = (long) i*i*i + (long) j*j*j;
043                this.i = i;
044                this.j = j;
045        }
046
047        public int compareTo(XTaxicab that) {
048                if      (this.sum < that.sum) return -1;
049                else if (this.sum > that.sum) return +1;
050                else                          return  0;
051        }
052
053        public String toString() {
054                return sum + " = " + i + "^3 + " + j + "^3";
055        }
056
057
058        public static void main(String[] args) {
059
060                int N = Integer.parseInt(args[0]);
061
062                // initialize priority queue
063                MinPQ<XTaxicab> pq = new MinPQ<>();
064                for (int i = 1; i <= N; i++) {
065                        pq.insert(new XTaxicab(i, i));
066                }
067
068                // enumerate sums in ascending order, look for repeated sums
069                XTaxicab prev = new XTaxicab(0, 0);   // sentinel
070                while (!pq.isEmpty()) {
071                        XTaxicab s = pq.delMin();
072
073                        // sum is same as previous one
074                        if (prev.sum == s.sum) {
075                                StdOut.println(prev);
076                                StdOut.println(s);
077                        }
078                        prev = s;
079
080                        if (s.j < N) pq.insert(new XTaxicab(s.i, s.j + 1));
081                }
082        }
083
084}