CS21003 Algorithms ICS29003 Algorithms Laboratory |
Autumn 2012, L-T-P: 3-1-0 L-T-P: 0-0-3 |

## Programming Assignment 5

The

n-thcabtaxi numberCT(n) is the smallest positive integer that can be written as a sum of two integer cubes inndifferent ways. Ifm=a^{3}+b^{3}, we callaandbthe 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
Bfrom the user. The absolute values of the components are restricted to be less than or equal toB.- Use a min-heap
Hof capacityB. Each element in the heap stores a triple (a,b,s) withs=a^{3}+b^{3}. The heap ordering is with respect to the sums. The first componentais 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 anyain the range [1,B].- Initialize
Hto contain theBelements (a,-(a-1),a^{3}-(a-1)^{3}) fora= 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 fromH, then insert (a,next(b),s'), provided that a suitable next(b) exists. Notice that the sumsa^{3}+b^{3}andb^{3}+a^{3}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
sin the triple (a,b,s).- Mentally think about
Bsorted lists with thei-th list storing all triples (a,b,s) witha=i. The above algorithm is akin to theB-way merging of these lists using a min-heap.- The running time of the above algorithm is O(
B^{2}logB), 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^{2}).- 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 withkdifferent representations. You discarded all smaller numbers havingk-1 (or less) different representations, but you considered only the cases whereaandbsatisfy the boundB. If you increase the bound, you may discover other representations of these smaller numbers. For example, forB= 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)^3The 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)^3This is detected only when

B≥ 4746. Fortunately, however, the smallest sum of cubes of the forma^{3}+b^{3}is at least 3a^{2}-3a+ 1. Therefore, there exists a larger upper boundB'which validates the correctness of a find. We do not have to keep on searching for arbitrarily large values ofa. 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