CODEWITHSUNDEEP
javac++calgorithm
Ajeet Ganga
Ajeet Ganga

Reputation: 8653

Generate a series of numbers representing the smallest pow() result

Suppose next() is the function that generates this series:

 8
 9
 16
 25
 27
 32
 36
 49
 64
 81

Which is 

i=2,3,....
j=2,3,....
f(n) =   minimum( pow(i,j) )   &&   f(n) > f(n-1)

I could come up with this O(n) code. Is there a O(1) or O(lg n) solution to this?

    int m =2, n = 2;
    int last =4;

   void next() {
      int a=m+1,b=n+1;
      long t = pow(a,b);
      int ma = max(m,n);
      //cout<<" max = "<<ma<<endl;
      for(int i=2;i<=ma+1;++i){
         for(int j=2;j<=ma+1;++j){
            if(pow(i,j) > last && pow(i,j) <= t) {
             a=i,b=j;
             t = pow(i,j); 
            }
         }
      } 
      if(a>m) m=a;
      if(b>n) n=b;
      last = t;
      //cout<<"\t"<<a<<"\t"<<b<<"\t"<<pow(a,b)<<endl;
      cout<<" \t"<<pow(a,b)<<endl;
     return;
    }
}

Note : 1. When I was referring to complexity, I was talking only about one single call to next(). 2. Caching will of course be helpful, but can we think of lg-n space for caching ? Heck, everything is faster with caching. :) 3. I do not know for constant-space complexity if there exist a solution with O(lg-n), it is just my hunch that there could be..

Upvotes: 3

Views: 191

Answers (3)

Patashu
Patashu

Reputation: 21793

The approach I imagine for this is some kind of lazy construction of a sorted list of all power results via a generator.

Imagine an endless field of x^y results - x in one direction, y in another. Now imagine a path that goes from 2^2 (which we'll say is 1 for simplicity's sake), one east to 3^2, one southwest to 2^3, one south to 2^4, northeast twice, one east, southwest thrice, one south... etc etc, diagonally zig-zagging and moving outwards.

As you're moving through this zig-zag path over all x^ys, add them to an automatically sorted collection, which is O(nlogn) in total. However, we're lazy and want to stop as soon as possible.

When you're asked for the nth largest power, do zig-zags and build the collection, keeping track on each single zig-zag what the lowest value produced was. If the lowest value was greater than everything in the list below the nth place in the list currently, we know that we'll never insert a lower number into the list that would change the result we'd return - so we return it.

In addition, if you're asked for the nth largest power, you can check right away if the lowest value is low enough to change the value and immediately return if it's not.

This algorithm is suboptimal because the powers grow faster in one direction than in the other - so a path that was biased to cover more values in the slower growing direction than the faster growing direction would need to search less values to return the nth largest power.

Upvotes: 0

user2167483
user2167483

Reputation:

Example python code, obviously not perfect, but does show how to do a lazy iteration. Memory usage is O(number of items served), and for time, multiply by a log of that.

import heapq

def power_seq(min_b, min_p):
    heap = []
    in_heap_table = {}
    cur_b, cur_p = min_b, min_p 
    heapq.heappush(heap, (power_value(cur_b, cur_p), cur_b, cur_p))
    in_heap_table[power_value(cur_b, cur_p)] = True
    while True:
        power, cur_b, cur_p = heapq.heappop(heap)
        yield power,cur_b, cur_p
        new_b = cur_b + 1
        new_p = cur_p + 1

        if power_value(new_b, cur_p) not in in_heap_table:
            heapq.heappush(heap, (power_value(new_b, cur_p), new_b, cur_p))
            in_heap_table[power_value(new_b, cur_p)] = True

        if power_value(cur_b, new_p) not in in_heap_table:
            heapq.heappush(heap, (power_value(cur_b, new_p), cur_b, new_p))
            in_heap_table[power_value(cur_b, new_p)] = True



# Can be made O(log p) if we want.
def power_value(b,p):
    power = 1
    while p >= 1:
        power = power*b
        p = p-1
    return power



def main():
    count = 0
    for tup in power_seq(2,2):
        print tup
        count += 1
        if count > 30:
            break

if __name__ == "__main__":
    main()

Upvotes: 1

trunklop
trunklop

Reputation: 383

(I don't know whether you aware of the fact your question is about the series of perfect numbers)

A brute force algorithm that MIGHT be faster: Generate all possible perfect powers in a given range and insert them into a sorted list. However, I don't know how many duplicates you have to expect. Definitely needs more memory than your approach but you didn't give any constraints :)

Upvotes: 0

Related Questions