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}