Enumerate an algebraic expression in increasing order

Question

I have the following expression: (2^i * 3^j), i,j >=0 and I need to enumerate it in increasing order i.e. 1 2 3 4 6 8 9 12 ....

I was thinking of doing the following: Maintain a priority queue. For current (i,j), we can either increment i or increment j. Compute the expression for these new values and push them into the priority queue. Pop from the queue and continue. We start with (0,0). We'll also need to maintain (i,j) along with the computed expression. Also, need to disregard duplicates.

I wanted to know if there was a faster way to enumerate the above expression, by maintaining lesser state?

Answer 1

Something along these lines.

 results = [1]
 i_index = 0
 j_index = 0 
 for(count=0, count<n, count ++){
     i_incr = results[i_index]*2  // next value of expression by incrementing i
     j_incr = results[j_index]*3  // next value of expression by incrementing j
     if (i_incr > j_incr)
         results << j_incr
         j_index += 1
     else if (i_incr < j_incr)
         results << i_incr
         i_index += 1
     else
        results << i_incr
        i_index += 1
        j_index += 1
     end
  }

The state is maintained by i_index and j_index, they keep track of the last value that has not been incremented for those indices resp. .