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

Pages: 1 2

### 3 Responses to “Sum Of Perfect Powers”

1. chaw said

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)) ```

``` ((1 (0 2 1 2)) (2 (1 2 1 2)) (3 #f) (4 (0 2 2 2)) (5 (1 2 2 2)) (6 #f) (7 #f) (8 (0 2 2 3)) (9 (0 2 3 2)) (10 (1 2 3 2)) (11 #f) (12 (2 2 2 3)) (13 (2 2 3 2)) (14 #f) (15 #f) (16 (0 2 2 4)) (17 (1 2 2 4)) (18 #f) (19 #f) (20 (2 2 2 4)) (21 #f) (22 #f) (23 #f) (24 (2 3 2 4)) (25 (0 2 5 2)) (26 (1 2 5 2)) (27 (0 2 3 3)) (28 (1 2 3 3)) (29 (2 2 5 2)) (30 #f) (31 (2 2 3 3)) (32 (0 2 2 5)) (33 (1 2 2 5)) (34 #f) (35 (2 3 3 3)) (36 (0 2 6 2)) (37 (1 2 6 2)) (38 #f) (39 #f) (40 (2 2 6 2)) (41 (2 4 5 2)) (42 #f) (43 (2 4 3 3)) (44 (2 3 6 2)) (45 #f) (46 #f) (47 #f) (48 (2 4 2 5)) (49 (0 2 7 2)) (50 (1 2 7 2)) (51 #f) (52 (2 4 6 2)) (53 (2 2 7 2)) (54 #f) (55 #f) (56 #f) (57 (2 3 7 2)) (58 #f) (59 #f) (60 #f) (61 #f) (62 #f) (63 #f) (64 (0 2 2 6)) (65 (1 2 2 6)) (66 #f) (67 #f) (68 (2 2 2 6)) (69 #f) (70 #f) (71 #f) (72 (2 3 2 6)) (73 #f) (74 #f) (75 #f) (76 #f) (77 #f) (78 #f) (79 #f) (80 (2 4 2 6)) (81 (0 2 3 4)) (82 (1 2 3 4)) (83 #f) (84 #f) (85 (2 2 3 4)) (86 #f) (87 #f) (88 #f) (89 (2 3 3 4)) (90 #f) (91 #f) (92 #f) (93 #f) (94 #f) (95 #f) (96 (2 5 2 6)) (97 (2 4 3 4)) (98 #f) (99 #f) (100 (0 2 10 2))) ```

2. Zack said

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

``````for z = 2:round(Int64, sqrt(x))
y = 0
m = 2

while y <= x
y = z^m
if y == x; return z, m; end
m += 1
end
end

return -1, -1
``````

end

function IsSumOfPerfectPowers(x::Integer)
for x1 = 1:div(x, 2)
a, m = IsPerfectPower(x1)

``````    if a != -1
x2 = x - x1
b, n = IsPerfectPower(x2)
if b != -1; return a, m, b, n; end
end
end

return -1, -1, -1, -1
``````

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!

3. Daniel said

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:

```1 = 1^2 + 0^2
2 = 1^2 + 1^2
4 = 2^2 + 0^2
5 = 2^2 + 1^2
8 = 2^2 + 2^2
9 = 2^3 + 1^2
10 = 3^2 + 1^2
12 = 2^3 + 2^2
13 = 3^2 + 2^2
16 = 2^3 + 2^3
17 = 2^4 + 1^2
18 = 3^2 + 3^2
20 = 2^4 + 2^2
24 = 2^4 + 2^3
25 = 3^2 + 2^4
26 = 5^2 + 1^2
27 = 3^3 + 0^2
28 = 3^3 + 1^2
29 = 5^2 + 2^2
...
```