# How many ways can I express $X$ as a sum unique natural numbers to the power of $N$

I also posted the problem here on Stackoverflow: http://ejj.mobi/g5i5gh but that was concerned with the programming solution. Now I am much more interested in the theory behind this problem, or rather the fact that I don't understand it.

Problem

Given two integers $X$ and $N$ how many ways can you express $X$ as a sum of the $Nth$ powers of unique natural numbers.

My Solution

Compute a range of numbers $1 .. r$ where $r$ is the largest number $< X$ that could possibly be included in its sum. (i.e. for an $X$ of 10 the range would be $1..3$ because $4^2 > 10$. After finding this range I would raise it to the power of $N$ it.

From this range I computed the permutations of all subsets of $1..r$. So $1..3$ generated $[1],[4],[9],[1,4],[1,9],[4,9],[1,4,9]$ then the number of ways to express $X$ by powers of $N$ was simply the number of permutations that summed to $X$; in this case $[1,9]$

In my opinion this is a terrible solution: it's brute-force and inelegant, there has to be a more elegant way that uses a relationship that I can't [don't] see. Any ideas/suggestions would be appreciated.

-
Your solution seems to focus on squares, while the problem statement focuses on powers of $N$. If $N=3$ you would be interested in $1,3,9,27\dots$ – Ross Millikan Oct 15 '13 at 13:52
Sorry, that is a pretty vague statement. I used $N = 2$ in my example, but you are correct if $N$ were 3 I would be interested in cubes. – Hunter McMillen Oct 15 '13 at 13:54
No, powers of N (for N=2) are $1,2,4,8\dots$ If you want $N$th powers of naturals, you should say that. – Ross Millikan Oct 15 '13 at 13:56
@RossMillikan Thanks, I'll update. – Hunter McMillen Oct 15 '13 at 13:57

I don't have a simple formula, but dynamic programming will make this easier. You can use the fact that the sum of the squares up to $k$ is $\frac 16k(k+1)(2k+1)$ So as you were, find the greatest $r$ such that $r^2 \le X$. If the sum of all the squares up to $r-1$ is less than $X$, you must have $r$ in the list. In your example, because $1+4 \lt 10$, you must have $3^2$ because you can't get there otherwise. Taking a larger example, let $X=1000$, so $r=31$ The sum of the smaller squares is larger than $1000$ you can get by without $31$. The number of representations is then the number of representations of $1000-31^2=39$ plus the number of representations of $1000$ using squares no larger than $30$. You need to be prepared for failure-$39$ has no such representation. The sum of the squares gets larger than $1000$ at $14$, so you have to start with a number at least that large.