fork download
copy 
  1. import java.util.List;
  2. import java.util.LinkedList;
  3. import java.util.Arrays;
  4. import java.util.PriorityQueue;
  5.  
  6. /**
  7.  * Taxicab number is the one that can be represented as a sum of cubes
  8.  * of two numbers in two different ways: a^3 + b^3 = c^3 + d^3 = N, where
  9.  * (a, b) and (c, d) pairs differ not only in the ordering.
  10.  *
  11.  * The basic idea is to enumerate all pairs (i, j) for 1 < i, j < N
  12.  * and find the ones that are repeated more than once. An easy way to
  13.  * do this is to store every pair in the array, sort the array and
  14.  * traverse it looking for the repeated pairs.
  15.  *
  16.  * But actually we can do a lot better in terms of extra memory used.
  17.  * We could use a PQ at first to store the pairs from (1, 1) to (N, N)
  18.  * and then traverse it adding new elements that would be traversed later
  19.  * on fly.
  20.  *
  21.  * (1, 1) (1, 2) ... (1, N)
  22.  * (2, 1) (2, 2) ... (2, N)
  23.  * ...
  24.  * (N, 1) (N, 2) ... (N, N)
  25.  *
  26.  * In each cell (i, j) there is a value i^3 + j^3. The thing is that
  27.  * in every row and in every column the values are sorted in the increasing
  28.  * order. And the elements from the matrix could be traversed in the
  29.  * following order: (1, 1), (2, 1), (2, 2), (3, 1), (3, 2) and so on.
  30.  *
  31.  * So after retrieving a next element from the PQ we can add a new
  32.  * one that would be by one cell lower in the matrix. Thus we will maintain
  33.  * the number of elements stored in the PQ at N and also as a result
  34.  * we will traverse every single element from the matrix under the main
  35.  * diagonal in the increasing order.
  36.  */
  37. class TaxicabNumbers {
  38.     /**
  39.      * Finds every taxicab number that is less than {@code n} in
  40.      * O(N^2lgN) time and using O(N^2) extra space
  41.      */
  42.     public static List<TaxicabNumber> taxicabNumbersSortVersion(int n) {
  43.         // 0 is not a taxicab number, so we can safely skip it
  44.         if (n <= 0) {
  45.             throw new IllegalArgumentException(String.format(
  46.                 "Expected: n > 0. Got: %d.", n));
  47.         }
  48.         List<TaxicabNumber> taxicabNumbers = new LinkedList<>();
  49.  
  50.         // find an upper bound for n^(1/3)
  51.         int maxPairNumber = 1;
  52.         while (pow(maxPairNumber, 3) <= n) {
  53.             maxPairNumber++;
  54.         }
  55.  
  56.         // 1 + 2 + 3 + ... + n = n * (n + 1) / 2
  57.         // 'cause we ignore the elements above the main diagonal
  58.         IntPair[] pairs
  59.             = new IntPair[maxPairNumber * (maxPairNumber + 1) / 2];
  60.  
  61.         for (int i = 0, iArray = 0; i < maxPairNumber; i++) {
  62.             // ignore the elements above the main diagonal
  63.             for (int j = 0; j <= i; j++) {
  64.                 pairs[iArray] = new IntPair(i, j);
  65.                 iArray++;
  66.             }
  67.         }
  68.         Arrays.sort(pairs);
  69.  
  70.         // the number of pairs with equal sums in a row
  71.         int runningNumber = 1;
  72.         IntPair prev = new IntPair(0, 0);
  73.         for (int i = 0; i < pairs.length; i++) {
  74.             IntPair curr = pairs[i];
  75.             if (prev.sum == curr.sum) {
  76.                 runningNumber++;
  77.                 if (runningNumber == 2) {
  78.                     taxicabNumbers.add(new TaxicabNumber(prev, curr));
  79.                 }
  80.             } else {
  81.                 runningNumber = 1;
  82.             }
  83.             prev = curr;
  84.         }
  85.         return taxicabNumbers;
  86.     }
  87.  
  88.     public static List<TaxicabNumber> taxicabNumbersHeapVersion(int n) {
  89.         if (n <= 0) {
  90.             throw new IllegalArgumentException(String.format(
  91.                 "Expected: n > 0. Got: %d.", n));
  92.         }
  93.         List<TaxicabNumber> taxicabNumbers = new LinkedList<>();
  94.         PriorityQueue<IntPair> pairs = new PriorityQueue<>();
  95.  
  96.         // find an upper bound for n^(1/3)
  97.         int maxPairNumber = 1;
  98.         while (pow(maxPairNumber, 3) < n) {
  99.             maxPairNumber++;
  100.         }
  101.  
  102.         for (int i = 0; i <= maxPairNumber; i++) {
  103.             pairs.offer(new IntPair(i, i));
  104.         }
  105.         // the number of pairs with equal sums in a row
  106.         int runningNumber = 1;
  107.         IntPair prev = new IntPair(0, 0);
  108.         while (!pairs.isEmpty()) {
  109.             IntPair curr = pairs.poll();
  110.             if (prev.sum == curr.sum) {
  111.                 runningNumber++;
  112.                 if (runningNumber == 2) {
  113.                     taxicabNumbers.add(new TaxicabNumber(prev, curr));
  114.                 }
  115.             } else {
  116.                 runningNumber = 1;
  117.             }
  118.             if (curr.i < maxPairNumber) {
  119.                 pairs.offer(new IntPair(curr.i + 1, curr.j));
  120.             }
  121.             prev = curr;
  122.         }
  123.         return taxicabNumbers;
  124.     }
  125.  
  126.     private static long pow(long x, int n) {
  127.         assert n >= 0;
  128.  
  129.         long pow = 1;
  130.         for (int i = 0; i < n; i++) {
  131.             pow *= x;
  132.         }
  133.         return pow;
  134.     }
  135.  
  136.     private static class IntPair implements Comparable<IntPair> {
  137.         private long i;
  138.         private long j;
  139.         private long sum;
  140.  
  141.         public IntPair(long i, long j) {
  142.             assert i > 0 && j > 0;
  143.  
  144.             this.i = i;
  145.             this.j = j;
  146.             sum = i * i * i + j * j * j;
  147.         }
  148.  
  149.         /**
  150.          * (a, b) &lt; (c, d) iff a^3 + b^3 ^lt; c^3 + d^3, or
  151.          * in case the sums are equal, then the smaller pair is the
  152.          * one that has smaller value on the first place (that is
  153.          * a &lt; c)
  154.          */
  155.         @Override
  156.         public int compareTo(IntPair other) {
  157.             int sumComparison = Long.compare(this.sum, other.sum);
  158.             if (sumComparison == 0) {
  159.                 return Long.compare(this.i, other.i);
  160.             } else {
  161.                 return sumComparison;
  162.             }
  163.         }
  164.  
  165.         @Override
  166.         public String toString() {
  167.             return String.format("%d^3 + %d^3", i, j);
  168.         }
  169.     }
  170.  
  171.     private static class TaxicabNumber {
  172.         private IntPair representation1;
  173.         private IntPair representation2;
  174.  
  175.         public TaxicabNumber(IntPair representation1,
  176.                 IntPair representation2) {
  177.             assert representation1.sum == representation2.sum;
  178.  
  179.             this.representation1 = representation1;
  180.             this.representation2 = representation2;
  181.         }
  182.  
  183.         @Override
  184.         public String toString() {
  185.             return String.format("%s = %s = %d", representation1,
  186.                 representation2, representation1.sum);
  187.         }
  188.     }
  189.  
  190.     public static void main(String[] args) {
  191.         System.out.println(taxicabNumbersSortVersion(65_000));
  192.         System.out.println(taxicabNumbersHeapVersion(65_000));
  193.     }
  194. }
  195.  
Success #stdin #stdout 0.1s 34416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0^3 + 0^3 = 0^3 + 0^3 = 0, 10^3 + 9^3 = 12^3 + 1^3 = 1729, 15^3 + 9^3 = 16^3 + 2^3 = 4104, 20^3 + 18^3 = 24^3 + 2^3 = 13832, 24^3 + 19^3 = 27^3 + 10^3 = 20683, 30^3 + 18^3 = 32^3 + 4^3 = 32832, 33^3 + 15^3 = 34^3 + 2^3 = 39312, 33^3 + 16^3 = 34^3 + 9^3 = 40033, 30^3 + 27^3 = 36^3 + 3^3 = 46683, 36^3 + 26^3 = 39^3 + 17^3 = 64232, 33^3 + 31^3 = 40^3 + 12^3 = 65728]
[0^3 + 0^3 = 0^3 + 0^3 = 0, 10^3 + 9^3 = 12^3 + 1^3 = 1729, 15^3 + 9^3 = 16^3 + 2^3 = 4104, 20^3 + 18^3 = 24^3 + 2^3 = 13832, 24^3 + 19^3 = 27^3 + 10^3 = 20683, 30^3 + 18^3 = 32^3 + 4^3 = 32832, 33^3 + 15^3 = 34^3 + 2^3 = 39312, 33^3 + 16^3 = 34^3 + 9^3 = 40033, 30^3 + 27^3 = 36^3 + 3^3 = 46683, 36^3 + 26^3 = 39^3 + 17^3 = 64232, 33^3 + 31^3 = 40^3 + 12^3 = 65728]
https://ideone.com/1SqVXq
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!