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