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.

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: