Problem # 30 : The sum of powers

Any natural number can be expressed as the sum of mth powers of another set of natural numbers.

For example :
10 = 1 + 3 (square both)
12 = 2 + 1 + 1 + 1 + 1 (cube all)
97 = 3 + 4 (raise to the 4th power)

Write a program to express a given number as the sum of the mth powers of another set of natural numbers using a minimum number of numbers. For example 10 can also be expressed as 2 + 2 + 1 + 1 (all squared) but your program should only give the output above since there only 2 numbers are used while here 4 numbers are used.

Name the subrotine POWERS(M N) where N is the number to be split up and M is the power to which these numbers must be raised. Output the set of numbers and the total number of numbers to a cleared screen.

Since N must be represented as the sum of some numbers the minimum numbers used cannot be one. Thus if M=2 and N=25 valid output would consist of the numbers 3 and 4 (3²+4²=25) and NOT 5².

Sample Output
POWERS(2 25) should print
The numbers are :
3 4
Minimum numbers = 2

(Back to problems at The Vault )

LinkExchange Member