The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq
). Vector
is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.
for i = 1..n
pq.insert( Vector(i^3+i^3,i,i) )
prev = Vector(0, 0, 0)
while not pq.empty()
curr = pq.deleteMin()
if prev[0] == curr[0]
print curr[0] is a Taxicab number that can be expressed as
prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
prev = curr
if curr[2] < N
j = curr[2] + 1
pq.insert( Vector(curr[1]^3 + j^3, curr[1], j) )
I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?