Finding a specific member of an ascending list of whole number powers sequence.

Question

I've been tasked with writing a program to find a $a_k$ member of a sequence:

$ a_0=4=2^2, a_1=8=2^3, a_2=9=3^2, a_3=16=4^2=2^4, a_4=25=5^2, a_5=27=3^3, a_6=32=2^5 $

and so on. I've coded up a brute-force solution, which takes advantage of $m^n$s logarithmic contours for $m>2$ and $n>2$:

The checking for each following member goes right-to-left through the table below, checking max $m$ for every $n$ and filtering out the repeated values (i.e. $64=8^2=4^3=2^6$). However, the method is too slow for me and I was wondering if there was a way to get to that $a_k$ element ($1<=k<=10^6$) by expressing this sequence as a formula? Thanks in advance.

Answer 1

This problem seems difficult, see the information provided in OEIS. However, brute force approaches give some results.

One may for instance list all numbers satisfying your conditions, until a given maximal value, and then sort them. The maximal value must be large enough to reach $k$ values (it seems from experiments and OEIS that it should be close tp $k^2$).

The following Python code makes the job, if I am correct:

sqrt_max_val = 10**6
max_val = sqrt_max_val**2
values = set()

for i in range(2,sqrt_max_val):
        val = i*i
        while val<max_val:
                values.add(val)
                val *= i

print("nb values: "+str(len(values)))
for x in sorted(values):
        print(x)

Notice that it uses a set to avoid duplicates, and that a full answer would have to find sqrt_max_val automatically (by increasing it and adapting the range, typically). Many optimizations are still possible.

Answer 2

I figured out an algorithm to determine a_k for a given k.

It works in roughly log(k) time.

1. First I figured out an approach to calculate k for a given a where a_k < a < a_k+1.

The approach is to add in all the values for each power where that number is less than a. Each step adds in trunc(a^1/p) - 1.

Start with the squares, that also adds in all the 4th, 6th, 8th, 10th powers etc. that are also within the range.

Then add in the cubes - that also adds in 6th, 9th, 12th, 15. etc. Note especially that the 6th powers have been added in twice.

We get to the 4ths - and note they have already been added once - so they don't need to be added agan.

power 5 is then added which also adds in 10, 15, 20, etc. Note especially that power 10 has been added in twice from 2 and 5. and power 30 has been added in 3 times.

power 6 - has been added in twice so we need to subtract this number.

and so on.

I created a small program that tells you which powers needed to be added or subtracted through power 80 which should handle k up to a trillion. Here's the result of that program - a 1 next to a power means add in (trunc(a^1/power) - 1) - a negative 1 means to subtract it; a 0 means it neither needs to be added or subtracted.

2 1; 3 1; 4 0; 5 1; 6 -1; 7 1; 8 0; 9 0; 10 -1; 11 1; 12 0; 13 1; 14 -1; 15 -1; 16 0; 17 1; 18 0; 19 1; 20 0; 21 -1; 22 -1; 23 1; 24 0; 25 0; 26 -1; 27 0; 28 0; 29 1; 30 1; 31 1; 32 0; 33 -1; 34 -1; 35 -1; 36 0; 37 1; 38 -1; 39 -1; 40 0; 41 1; 42 1; 43 1; 44 0; 45 0; 46 -1; 47 1; 48 0; 49 0; 50 0; 51 -1; 52 0; 53 1; 54 0; 55 -1; 56 0; 57 -1; 58 -1; 59 1; 60 0; 61 1; 62 -1; 63 0; 64 0; 65 -1; 66 1; 67 1; 68 0; 69 -1; 70 1; 71 1; 72 0; 73 1; 74 -1; 75 0; 76 0; 77 -1; 78 1; 79 1; 80 0;

I coded that up as a small spread sheet and tested it against the OEIS sequence shown within https://oeis.org/A001597 - especially https://oeis.org/A001597/b001597.txt and it seems to work fine.

2. So now that we can calculate k from a, we now go the other way. We can get a first estimate of a_k from k^2. We plug that back into the formula in 1) above and see how far off k is. We make our new a = (the desired k adjusted by the difference in the formula from 1) ^ 2. Then keep iterating until we find an a that generates the desired k.

3. That a might not be the exact a_k. It's an a that is somewhere in the range a_k < a < a_k+1.

Probably quickest way to determine the exact a_k is to take the root of each power - truncate it, then raise it back to the power. The maximum of those values is the a_k that you desire.

I didn't code up steps 2 and 3 - but the approach above should work. The spreadsheet in step 1 works pretty instantaneously.