## Perfect Power Sequence

### February 16, 2018

Here’s our solution:

(define-generator (powers) (define-record-type power (fields val base expo)) (define (lt? a b) (< (power-val a) (power-val b))) (yield 1) (let loop ((pq (pq-insert lt? (make-power (expt 2 2) 2 2) pq-empty)) (m 3) (limit (expt 2 3)) (prev 0)) (if (and (not (pq-empty? pq)) ( (generator-take 54 (powers)) (1 4 8 9 16 25 27 32 36 49 64 81 100 121 125 128 144 169 196 216 225 243 256 289 324 343 361 400 441 484 512 529 576 625 676 729 784 841 900 961 1000 1024 1089 1156 1225 1296 1331 1369 1444 1521 1600 1681 1728 1764)

That requires a bit of explanation. `Pq`

is a priority queue that has members like `(val, base, expo)`

, one per power, ordered by increasing value. When the generator is just about to produce the perfect power 100, the priority queue consists of (100 10 2) (125 5 3) (243 3 5) (256 4 4) (729 3 6), which is one member for each power sequence; thus, 100 is the next square, 125 is the next cube, 243 is the next fifth power, 256 is the next fourth power, and 729 is the next sixth power. A new power sequence is added to the priority queue every time the sequence passes a new power of 2, so the priority queue will have log₂ *n* members when the sequence reaches a value of *n*. The code is careful to maintain duplicates, so that none of the individual power sequences is interrupted, but to print only one copy of any value.

You can run the program at https://ideone.com/XvXveK, where you will also see the code that handles generators and priority queues.

Here is my implementation in Julia.

function IsPerfectPower(x::Int64)

y = ceil(Int64, sqrt(x))

end

function genseq(n::Int64)

y = zeros(Int64, n)

y[1] = 1

end

Performance benchmark: on an Intel i7 laptop running on Win7, it generates the sequence of the PP numbers that are less or equal to 10000 in about 0.1 sec, using approx. 85 MB of RAM.

Typo in my previous commend: 85 Kilobytes, not MB… Sorry about that!

Two solutions in Python. I expected the first to be the fastest: merging already sorted sequences. But it turned out to be otherwise. The second is a little faster.

Here is some Java. It generates up to 10000 in around 60ms on a 3.3GHz i5 iMac:

The queue solution works nicely in Python:

It’s quite important how the queue is extended – doing

still works, but the queue gets much longer.

Incidentally, the code on the solution page seems to be garbled – I think WordPress have messed something up with angle brackets in code.

By the way, this is https://oeis.org/A001597

@matthew: I tried the priority method too and it worked nicely, but a little slow in Python. The method below takes about 0.1 sec for all powers below 10^9.

@Paul: did you do a speed comparison with my priority queue function above?

@matthew: I see now that your method works very fast (91 msec for yours and 121 ms for pp2 for all powers up to 10^9). I must have messed up something with my implementation.

@Paul: that’s about what I made it – also the queue uses less memory, I’m running the program just printing out all the numbers, up to 25528390307779969 after about 30 mins.

For the queue, as mentioned above, it’s significant how the queue is extended.

Here’s an implementation in C that uses the approach from the solution.

Output: