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.
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: