Programming Assignment 5

The n-th cabtaxi number CT(n) is the smallest positive integer that can be written as a sum of two integer cubes in n different ways. If m = a³ + b³, we call a and b the components of the sum. We allow the components in the sum to be positive, negative and zero. In this exercise, you locate as many cabtaxi numbers as possible.

• Read a positive integral bound B from the user. The absolute values of the components are restricted to be less than or equal to B.
• Use a min-heap H of capacity B. Each element in the heap stores a triple (a,b,s) with s = a³ + b³. The heap ordering is with respect to the sum s. The first component a is in the range [1,B]. The second component may be positive, negative or zero. At any point of time, the heap must store (at most) one triple (a,b,s) for any a in the range [1,B].
• Initialize H to contain the B elements (a, -(a-1), a³-(a-1)³) for a = 1,2,...,B. You do not need heapify() or makeheap() for this initialization.
• Then, run a loop of one deletemin() followed (usually) by one insert(). More precisely, if (a,b,s) is deleted from H, then insert (a,next(b),s'), provided that a suitable next(b) exists. Notice that the sums a³ + b³ and b³ + a³ are treated as the same representation. Avoid duplicate insertion of items in the heap.
• Locate the cabtaxi numbers in the above loop.

More information

• A note on taxicab and cabtaxi numbers
• You need a 64-bit integer for storing s in the triple (a,b,s).
• Mentally think about B sorted lists with the i-th list storing all triples (a,b,s) with a = i. The above algorithm is akin to the B-way merging of these lists using a min-heap.
• The running time of the above algorithm is O(B² log B), and its space requirement is only Θ(B). An obvious algorithm to solve the same problem is to generate all tuples (a,b,s), store them in an array, sort the array, and make one pass through the array. This algorithm too runs in the same time, but its space requirement is Θ(B²).
• For a given bound B, the reported cabtaxi numbers may fail to be the correct cabtaxi numbers. Suppose that you have generated CT(k) as the first number you encounter with k different representations. You discarded all smaller numbers having k-1 (or less) different representations, but you considered only the cases where a and b satisfy the bound B. If you increase the bound, you may discover other representations of these smaller numbers. For example, for B = 3000, we erroneously discover the sixth cabtaxi number as:

     CT(6) = 3080802816
           = (1480)^3 + (-544)^3
           = (1968)^3 + (-1656)^3
           = (81)^3 + (1455)^3
           = (456)^3 + (1440)^3
           = (904)^3 + (1328)^3
           = (1672)^3 + (-1168)^3
  

  The correct value of CT(6) is, however, the following:

     CT(6) = 1412774811
           = (804)^3 + (963)^3
           = (1155)^3 + (-504)^3
           = (2115)^3 + (-2004)^3
           = (1246)^3 + (-805)^3
           = (1134)^3 + (-357)^3
           = (4746)^3 + (-4725)^3
  

  This is detected only when B ≥ 4746. Fortunately, however, the smallest sum of cubes of the form a³ + b³ is at least 3a² - 3a + 1. Therefore, there exists a larger upper bound B' which validates the correctness of a find. We do not have to keep on searching for arbitrarily large values of a. You do not have to implement this check.

Sample output

   Enter bound B: 100
   CT(1) = 1
         = (1)^3 + (0)^3
   CT(2) = 91
         = (6)^3 + (-5)^3
         = (3)^3 + (4)^3
   CT(3) = 728
         = (12)^3 + (-10)^3
         = (6)^3 + (8)^3
         = (9)^3 + (-1)^3

Submission Site

---

Back | Home