Sum Of Perfect Powers
August 31, 2018
I think this must be somebody’s homework:
Write a program to determine if a number x can be written as the sum of two perfect powers. This is, given x determine if there exist non-negative integers a, b, m and n such that am + bn = x where 1 ≤ x ≤ 106 and m > 1 and n > 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.
Programming Praxis 
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).
(import (scheme base) (only (srfi 1) cons* iota)) ;; (b n) s.t. b^n = k; #f if none such. ;; integers k >= 1, b >= 0, n >= 2. ;; (perfect-power 125) => (5 3) (define (perfect-power k) (if (< k 2) (list 1 2) (let loop ((b 2) (n 2)) (and (< b k) (let ((bn (expt b n))) (cond ((= bn k) (list b n)) ((< bn k) (loop b (+ n 1))) (else (loop (+ b 1) 2)))))))) ;; (a m b n) s.t. a^m + b^n = k, with a^m <= b^n; #f if none such. ;; integers a, b >= 0; m, n >= 2. (define (sum-perfect-powers k) ;; check for a^m = 0 or a^m = 1 cases first. (cond ((perfect-power k) => (lambda (bn) (cons* 0 2 bn))) ((and (> k 1) (perfect-power (- k 1))) => (lambda (bn) (cons* 1 2 bn))) ;; a^m > 1 (else (let loop ((a 2) (m 2)) (and (< a k) (let ((am (expt a m))) (if (<= (* 2 am) k) (let ((bn (perfect-power (- k am)))) (if bn (cons* a m bn) (loop a (+ m 1)))) (loop (+ a 1) m)))))))) ;; Demo (map (lambda (i) (list i (sum-perfect-powers i))) (iota 100 1))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.
from itertools import count def isqrt(n): x = n while True: y = (x + (n // x)) // 2 if y - x in (0, 1): return x x = y def calc_pp_sum(x): if x < 1: return None pps = {} for y in range(0, isqrt(x) + 1): for z in count(2): pp = y ** z if pp > x: break pps[pp] = (y, z) if x - pp in pps: return (y, z) + pps[x - pp] if y <= 1: break return None for x in count(0): pp_sum = calc_pp_sum(x) if pp_sum: print("{} = {}^{} + {}^{}".format(x, *pp_sum))Output: