// Ramanujans Taxi Problem:
// Finde ganzzahlige Loesungen von i^3+j^3=k^3+l^3
// http://www.durangobill.com/Ramanujan.html
public class taxi {
    private static class pairs {
        int i;
        int j;
        pairs next;
        pairs (int i, int j, pairs next) {
            this.i = i;
            this.j = j;
            this.next = next;
        }
        public String toString() {
            String s=" = "+i+"^3+"+j+"^3";
            if (next != null)
                s+=next;
            return s;
        }
    }
    public static int cube(int i) {
        return i*i*i;
    }
    public static void main(String [] args) {
        int limit = Integer.parseInt(args[0]);
        // ListTable<Integer,pairs> t = new ListTable<Integer, pairs>();
        // HashTable<Integer,pairs> t = new HashTable<Integer, pairs>();
        // HashTable<Integer,pairs> t = 
        //    new HashTable<Integer, pairs>((int)Math.round(Math.pow((double)limit,2.0/3.0)/5.0)+1);
        TreeTable<Integer,pairs> t = new TreeTable<Integer,pairs>();
        int count = 0;
        for (int i=1; cube(i)<limit/2; i++)
            for (int j=i; cube(i)+cube(j)<limit; j++) {
                int num=cube(i)+cube(j);
                pairs p=t.get(num);
                count++;
                if (p == null) {
                    t.put(num, new pairs(i,j,null));
                } else {
                    p.next = new pairs(i,j,p.next);
                    System.out.println(num+p.toString());
                }
            }
        System.out.println("Innere main-Iterationen: "+count); // O(limit^(2/3)) Iterationen
        System.out.println("Listenlaenge: "+t.nodecount);
        System.out.println("get-Iterationen: "+t.getitcount);
    }                
}