## Sum Of Perfect Powers

### August 31, 2018

I think this must be somebody’s homework:

Write a program to determine if a number

xcan be written as the sum of two perfect powers. This is, givenxdetermine if there exist non-negative integersa,b,mandnsuch thata+^{m}b=^{n}xwhere 1 ≤x≤ 10^{6}andm> 1 andn> 1.

Your task is to write a program that determines if a number is a sum of two perfect powers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: