## Sum Of Perfect Powers

### August 31, 2018

We build a list of the perfect powers less than a million. Then we can determine if *x* can be expressed as the sum of perfect powers by scanning through the list and checking if both the current item *k* and *x* − *k* are both in the list. The list of perfect powers is computed when the function is defined:

(define sum-of-perfect-powers (let ((xs (unique = (sort < (list-of (expt x n) (x range 1 1001) (n range 2 20) (<= (expt x n) 1000000)))))) (lambda (x) (let loop ((xs xs)) (if (null? xs) #f (if (member (- x (car xs)) (cdr xs)) (list (car xs) (- x (car xs))) (loop (cdr xs))))))))

There are 1111 perfect powers in *xs*. Here are some examples:

> (sum-of-perfect-powers 25) (9 16) > (sum-of-perfect-powers 26) (1 25) > (sum-of-perfect-powers 27) #f

You can run the program at https://ideone.com/K3wjrq.

Advertisements

Here is a solution in standard Scheme that does not precompute powers

and so is a bit more general than required by the question.

Unless I misread the question, I believe the result of

@programmingpraxis’s solution for 27 (and similar cases) is not

correct. Since a, b are not required to be greater than zero (only

nonnegative), we have 0^2 + 3^3 = 27 as an option (among many others).

Interesting drill. I don’t understand why x needs to be less or equal to 1e6, so my code doesn’t have this unnecessary limitation. Here is my take on it using Julia 1.0.

Code:

function IsPerfectPower(x::Integer)

if x == 1; return 1, 2; end

end

function IsSumOfPerfectPowers(x::Integer)

for x1 = 1:div(x, 2)

a, m = IsPerfectPower(x1)

end

Examples:

julia> IsSumOfPerfectPowers(17)

(1, 2, 2, 4) # 1^2 + 2^4 = 17

julia> IsSumOfPerfectPowers(1000000)

(280, 2, 960, 2) # a Pythagorean set

julia> IsSumOfPerfectPowers(17233)

(-1, -1, -1, -1) # so, no

Have a nice Labor Day weekend!

Here’s a solution in Python.

Output: