CareerCup

Given a number n, if at all it can be written as ab (b > 1), then b<log(n)+1. And for every fixed b, checking if there exists an a with ab=n can be done using binary search. The total running time is therefore O((logn)^2) I guess.

from cstheory.stackexchange.com/questions/2077/how-to-check-if-a-number-is-a-perfect-power-in-polynomial-time

This is very similar to Jason's idea, but I didn't preprocess all of the 2^n values.

1) Use a minheap
2) Upon reset (or instantiation), make sure heap is cleared with 4 on the top with {2,2} for m^n as metadata.
3) When next is called, pop the min and add 8 {2,3} and 9 {3,2}
4) Repeat for {m,n+1} when you pop {m,n}. If a {m,2} is popped, then add {m+1,2}
5) For any existing values, push {m,n+2} instead
6) Rinse and repeat for each next().

Any idea on logic for generating the power sequence ??

from __future__ import generators
from pprint import pprint

def mypower():
    # cache of all presented numbers
    presented = set()
    # list of m and its current n not yet generated
    elist = []
    # first m = 2, n = 2
    elist.append([2, 2])
        
    while True:
        min_idx = -1
        min_v = 0
        for i, e in enumerate(elist):
            m, n = e
            v= m**n
            if min_v == 0 or min_v > v:
                min_v = v
                min_idx = i

        presented.add(min_v)
        # expand elist only if min_idx is the last guy in elist 
        # and we export its m^n in this run 
        if elist[min_idx][1] == 2:
            nextguy = elist[min_idx][0]+1
            # use cache to prevent duplicate
            while nextguy in presented:
                nextguy += 1
            elist.append([nextguy, 2])
            
        elist[min_idx][1] += 1
        pprint (elist)
        #print min_v
        print "="*20
        print min_v
        yield min_v
        
if __name__ == '__main__':
    a = mypower()
    while True :
        a.next()

####### print out

[[2, 3], [3, 2]]
====================
4
[[2, 4], [3, 2]]
====================
8
[[2, 4], [3, 3], [5, 2]]
====================
9
[[2, 5], [3, 3], [5, 2]]
====================
16
[[2, 5], [3, 3], [5, 3], [6, 2]]
====================
25
[[2, 5], [3, 4], [5, 3], [6, 2]]
====================
27
[[2, 6], [3, 4], [5, 3], [6, 2]]
====================
32
[[2, 6], [3, 4], [5, 3], [6, 3], [7, 2]]
====================
36
[[2, 6], [3, 4], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
49
[[2, 7], [3, 4], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
64
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 2]]
====================
81
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 3], [11, 2]]
====================
100
[[2, 7], [3, 5], [5, 3], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]
====================
121
[[2, 7], [3, 5], [5, 4], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]
====================
125
[[2, 8], [3, 5], [5, 4], [6, 3], [7, 3], [10, 3], [11, 3], [12, 2]]

<pre lang="" line="1" title="CodeMonkey11712" class="run-this">package linkedin;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class NextPowers implements Iterator<Long> {
private static class IntPair {
public IntPair(int a, int b) {
this.a = a;
this.b = b;
}
public int a;
public int b;

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[').append(a).append(',').append(b).append(']');

return sb.toString();
}
}
private ArrayList<IntPair> elems = new ArrayList<IntPair>();
private HashSet<Integer> preSet = new HashSet<Integer>();

public NextPowers () {
elems.add(new IntPair(2, 2));
}

public void reset() {
elems.clear();
preSet.clear();
elems.add(new IntPair(2, 2));
}

@Override
public boolean hasNext() {
return true;
}

private long prev = -1;
@Override
public Long next() {
long n = next_();
while (n == prev) {
prev = n;
n = next_();
}
prev = n;
return n;
}
public long next_() {
long min = Long.MAX_VALUE;
int minI = Integer.MAX_VALUE;
for (int i = 0; i < elems.size(); ++i) {
IntPair ip = elems.get(i);
long v = (long)Math.pow(ip.a, ip.b);
if (v < min) {
min = v;
minI = i;
}
}
IntPair ip = elems.get(minI);
preSet.add(ip.a);
if (ip.b == 2) {
ip.b = 3;
elems.add(new IntPair(ip.a + 1, 2));
} else {
ip.b ++;
}

return min;
}

@Override
public void remove() {
// TODO Auto-generated method stub

}

public static void main(String[] args) {
NextPowers np = new NextPowers();
for (int i = 0; i < 20; ++i) {
System.out.println(np.next());
}
}
}
</pre><pre title="CodeMonkey11712" input="yes">
</pre>

private long n = 4;
private int i = 2;
public Long next() {
        long j = n;
        for (j = n; j < n * n; j++) {
            for (int k = i; k < n; k++) {
                int s = (int) (Math.log(j) / Math.log(k));
                if ((Math.log(j) / Math.log(k)) == s) {
                    n = j + 1;
                    return j;
                }
            }
        }
        return n;
    }

using a priority queue or min-heap, stores the values of 2^2, 2^3, 2^4, .... 2^32. In each iterator, return the first element in the queue/heap, suppose the element is a^b, push (a+1)^b into the queue/heap. It takes (O(32log32)) to initialize the queue/heap, and each query takes O(log32) steps.