CS problem, turned to mathematics

Question

I am trying to solve some of the projecteuler problems using a much of a programmers approach. However, I would like to get more into the math, and therefore would try to do some mathematical reasoning to this specific projecteuler exercise:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

$ 1634 = 1^4 + 6^4 + 3^4 + 4^4 $

$ 8208 = 8^4 + 2^4 + 0^4 + 8^4 $

$ 9474 = 9^4 + 4^4 + 7^4 + 4^4$

As $ 1=1^4$ is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

---

There are various ways of presenting a reasonable solution to this problem, using simple programming skills. However, I would like to be able to do the reasoning on pen and paper and not rely on the computational power. Can anybody tell me the steps of how to solve this problem with mathematical reasoning?

Answer 1

I would like to be able to do the reasoning on pen and paper and not rely on the computational power. Can anybody tell me the steps of how to solve this problem with mathematical reasoning?

For a problem of this type it is hard to guess if that is possible without first performing the computer search up to a proven upper bound on the solutions. If a search showed that there were a large number of solutions up to that bound, it would suggest that hand calculations and formal proofs could become complicated.

Sometimes the solution set has special structure that can be used in a theoretical solution, but this cannot always be seen before giving the problem to a computer.

Experiment usually precedes theory, and more so for number-theoretic problems where intuition is limited.

Answer 2

If a number $n$ has seven digits, the sum of fifth powers of digits is $\le 7\cdot 9^5<10^6\le n$ and with each additional digit the upper limit for the power-sum grows by at most $9^5$ whereas the lower lmit for $n$ grows by a factor of $10$. We conclude that $n$ has at most six digits.

Moreover, from $d^5\equiv d\pmod{10}$ we see that the sum of all but the last digit must be a multiple of $10$.

We not that $a<b$ implies $a^5+b^5<(a+1)^5+(b-1)^5$, i.e. a sum of fifth powers for a given sum of digits is maximized when the digits are as close togethre as possible (i.e. assume at most tow consecutive values).

From $6\cdot 9^5=354294$, we conclude that $n$

• has at most five digits (see below)
• or has leading digits $3$, $\le5$ and then at most four $9$s (contradiction: $4\cdot 9^5+5^5+3^5<350000$)
• or has leading digit $2$ and at most five nines, so $n\le 2^5+6\cdot 9^5=295277$. In fact from $2+4\cdot 9=38$, we conclude that the sum of the five leading digits is at most $30$ and thus $n\le 2^5+4\cdot 7^5+9^5=126309<200000$, so this case is not possible either
• or has leading digit $1$ and at most five nines. Like above the sum of the first five digits is a multiple of $10$, so either $=30$ or $\le 20$. In the latter case we get $n\le1^5+3\cdot 5^5+4^5+9^5=69449<10000$. Remains the case with digit sum $30$. Dropping the leading $1$, the sum $29$ can be obtained with four digits as: $9+9+9+2, 9+9+8+3, 9+9+7+4, 9+9+6+5,9+8+8+4,9+8+7+5,9+7+7+6,8+8+8+5,8+8+7+6, 8+7+7+7$. For each of these ten cases one can compute the sum of fifth powers of these digits and the leading $1$ and add $0^9,\ldots ,9^9$ for the last digit to check if a valid number occurs. - Only one solution is found this way

For the five-digit (or less) case a lot of more case distinctions are necessary, though much can still be gained from the condition that the sum of all but th elast digit is a multiple of ten. However, just learning from above the limit that $n<200000$ and then making a brute-force search, is probably the recommended way.