Sum of Nth Power in Python

Program to find the number of ways that a given integer can be represented as the sum of the Nth power of the unique, natural numbers. For example, if X = 100 and N = 2, we have to find all combinations of squares adding up to 100. The possible solutions are (100^2), (8^2+6^2), (1^2+3^2+4^2+5^2+7^2). So the total possible solutions are 3.

Python Program for Sum of Nth Power

def powersum(X, N, num):
    value = X-pow(num, N)
    if value<0: # if value is lessthan 0 then there is no solution 
        return 0
    elif value==0: # if value is equal 0 then there is excatly one solution
        return 1
    else: # Calculate the number of solution with/ without value
        return powersum(value, N, num+1)+powersum(X, N, num+1)



X = int(input("Enter the value of X: "))
N = int(input("Enter the value of N: "))
print(powersum(X, N, 1))

Output

Enter the value of X: 100
Enter the value of N: 2
3
Enter the value of X: 29
Enter the value of N: 2
2

Approach

  1. Check whether X is equal to 1 power N if so then there is only one possible solution.
  2. If X is less than 1 power N, then there is no possible solution.
  3. If X is greater than 1 power N, then return powersum(value, N, num+1)+powersum(X, N, num+1). The first call of powersum includes the 1 power N value and the second call excludes the 1 power N value.

Leave a Reply

Your email address will not be published. Required fields are marked *