Generate a sequence of numbers (powers) in order

Question

I'm looking for an algorithm (or better yet, code!) for a the generation of powers, specifically numbers with an odd exponent greater than 1: third powers, fifth powers, seventh powers, and so forth. My desired output is then

8, 27, 32, 125, 128, 216, 243, 343, 512, 1000

and so forth up to a specified limit.

I don't want to store the powers in a list and sort them, because I'm making too many to fit in memory -- hopefully the limit be 10³⁰ or so, corresponding to a memory requirement of ≈ 1 TB.

My basic idea is to have an array holding the current number (starting at 2) for each exponent, starting with 3 and going up to the binary log of the limit. At each step I loop through the exponent array, finding the one which yields the smallest power (finding either pow(base, exponent) or more likely exponent * log(base), probably memoizing these values). At that point call the 'output' function, which will actually do calculations with the number but of course you don't need to worry about that.

Of course because of the range of the numbers involved, bignums must be used -- built into the language, in a library, or self-rolled. Relevant code or code snippets would be appreciated: I feel that this task is similar to some classic problems (e.g., Hamming's problem of generating numbers that are of the form 2^x3^y5^z) and can be solved efficiently. I'm fairly language-agnostic here: all I'll need for my 'output' function are arrays, subtraction, bignum-word comparison, and a bignum integer square root function.

Answer 1

Your example is missing 64=4^3, and 729=9^3.

You want the set of all { n^m } traversed in numerical order, m odd, n integral and n > 1. We know that (for n > 1) that increasing either n or m will increase this value, but short of calculation we can't compare much else.

There are two obvious "dual" ways to do this: keep track of the highest base n you consider, and for all bases less than that, the next exponent m to consider. Then pick the smallest one, and compare it to n^3. Or, the other way around -- keep track of the highest exponent m, and for each exponent smaller than that, keep track of the highest base used, and find the smallest one, and compare it to adding 2^m.

To make keeping track of these numbers efficiently, you'll want to keep them in a priority queue. Now, you still want to minimize the number of entries in the priority queue at a time, so we'll want to figure out which of these two methods does better job of this. It turns out that much higher n values are required to make it to a given point. At number k, the largest value of m seen will be log_2 of k, whereas the largest value of n seen will be k^(1/3).

So, we have a priority queue with elements (v, n, m), where the value v=n^m.

add_priority_queue(2^3, 2, 3)
for m in 5, 7, ....
    v = 2^m
    while value(peek(queue)) <= v:
        (v1, n1, m1) = pop(queue)
        if v1 != v print v1
        add_priority_queue((n1+1)^m1, n1+1, m1)
    add_priority_queue(2^m, 2, m)

Note that we need to check for v1 = v: we can have 2^9 = 512 = 8^3, and only one should be printed out, right?

A Haskell implementation, with a random priority queue grabbed off of hackage.

import Data.MeldableHeap

dropMin q = maybe empty snd (extractMin q)

numbers = generate_values (insert (2^3, 2, 3) empty) 5

generate_values q m = case findMin q of
    Nothing -> []
    Just (v1, n1, m1) -> case compare v1 (2^m) of
        EQ -> generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        LT -> v1 : generate_values (insert ((n1+1)^m1, n1+1, m1) (dropMin q)) m
        GT -> 2^m : generate_values (insert (3^m, 3, m) q) (m + 2)

main = sequence_ (map print numbers)

I have a run currently at 177403008736354688547625 (that's 23 digits) and 1.3 GB plaintext output, after 8 minutes

Answer 2

deque numbers // stores a list of tuples - base number, and current odd power value - sorted by the current odd power value

for i = 2 .. infinity
  numbers.push_back (i,i^3) // has to be the highest possible number so far
  while numbers.peek_front[1] == i // front always has the lowest next value
    print i
    node = numbers.pop_front
    node[1]=node[1]*(node[0]^2)
    // put the node back into the numbers deque sorted by the second value in it - will end up being somewhere in the middle

at 2, numbers will be [2,8]

at 3, numbers will be [2,9], [3, 27] ... at 8, numbers will be [2,8], [3,27].....[8,8^3]

You'll take off the first node, print it out, then put it back in the middle of numbers with the values [2,32]

I think this will work and has a reasonable memory usage.

There's a special case for 1, since 1^N never changes. This will also print out duplicate values for numbers - 256 for instance - and there are fairly simple ways to slightly alter the algorithm to remove those.

This solution is constant time for checking each number, but requires quite a bit of ram.

Answer 3

Consider k lists for numbers 2 .. k+1 numbers. Each list i represents the powers of number i+1. Since each list is a sorted use k-way merging with min heap to achieve what you need.

Min-heap is constructed with first indices of lists as key and after minimum is extracted we remove first element making second element as key and rearrange the heap to get next minimum. This procedure is repeated till we get all numbers.