Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks. It took me awhile to digest what you wrote, but after that I was able to think out a pattern and generalize it. My solution is still not great compared to the others, but it did past to test cases. –  Hunter McMillen Oct 15 '13 at 18:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.