1

I am doing Project Euler # $30$. I currently want to find all the numbers that can be written as the sum of fifth powers of their digits. I solved this using a generic upper bound of a million. However, this isn't very precise and so I want to find out an upper bound on the largest number which can be written as the sum of the $n$th power of its digits. My original plan was to go with $10^{n + 1}$ but I don't think this is true for larger values of n.

For the love of maths
  • 2,368
  • 1
    This doesn't improve the upper bound itself, but you can efficiently reduce your search space by a factor of 10: If we write the decimal expansion of the integer $a$ as $(a_m \cdots a_1 a_0){10}$, then since $i^5 = i \pmod {10}$ (thanks to Fermat's Little Theorem), reducing the condition $$a = \sum{i=0}^m a_i^5$$ modulo $10$ gives $a_0 \equiv \sum_{i=0}^m a_i^5 \equiv \sum_{i=0}^m a_i \pmod {10}$ and so $$a_1 + \cdots + a_m \equiv 0 \pmod {10} ,$$ that is, we can determine, e.g., $a_1$ immediately in terms of $a_2, \ldots, a_m$. – Travis Willse Jun 27 '20 at 17:46

2 Answers2

3

Let $N$ be a generic $n$ digit number that satisfies that property. We can write $$N = a_1 + 10a^2 + \cdots + 10^{n-1}a_n$$ where each $a_i \in \{0, \ldots, 9\}$ and $a_n \neq 0$.

We have $$a_1 + 10a^2 + \cdots + 10^{n-1}a_n = a_1^5 + \cdots + a_n^5.$$

The right side can be bounded as $$a_1^5 + \cdots + a_n^5 \le n\cdot9^5.$$

The left side can be bounded (below) as \begin{align} a_1 + 10a^2 + \cdots + 10^{n-1}a_n &\ge 10^{n-1}a_n \ge 10^{n-1}. \end{align}

Thus, we see that $$10^{n-1} \le n\cdot 9^5.$$ The above is true only for $n \le 6$.

That gives an easy and reasonable upper bound.

Aryaman Maithani
  • 15,771
1

Digits are nonnegative integers. Fifth powers of nonnegative integers are nonnegative integers. Consequently, no negative number can be the sum of the fifth powers of its digits.

Zero is the sum of the fifth powers of its digits.

This leaves positive integers to consider.

Let $N$ be a positive integer and $d$ be the number of digits in $N$. So $$ 10^{d-1} \leq N \leq 10^d - 1 \text{.} $$ Since each digit is at most $9$ and at least $0$ and also at least one digit is not $0$ so is at least $1$, the sum of the fifth powers of the digits of $N$ is in the interval $[1,d9^5]$. For $N$ to equal the sum of the fifth powers of its digits, we require $$ 1 \leq N \leq d 9^5 \text{.} $$

These two intervals for $N$ have no intersection if either $10^d - 1 < 1$ or $d 9^5 < 10^{d-1}$. The first of these forces $d \leq 0$, forcing $N = 0$ so contradicts that $N$ is a positive integer, so we need not consider it further. The second condition is complicated to solve. Using the Lambert $W$ function, we can show $$ d < \frac{W_0 \left(\frac{-\ln 2 - \ln 5}{590490}\right)}{\ln 2 + \ln 5} = 1.69{\dots} \times 10^{-6} \\ \text{ or } d > -\frac{W_{-1} \left(\frac{-\ln 2 - \ln 5}{590490}\right)}{\ln 2 + \ln 5} = 6.59{\dots} \text{.} $$ (We'll come back to solving this. Using this method for $k^\text{th}$ powers of digits is infeasible.) The former again requires $N = 0$, so we do not consider it further. Labelling the bound in the latter, $M$, we have $10^M - 1 = 3\,891\,390.026{\dots}$. So if $N$ is greater than about $3.9$ million, $N$ cannot be the sum of the fifth powers of its digits. (This is close to the bound of $1$ million you used, but the potential exists that there are integers between $1$ million and this bound that are the sum of the fifth powers of their digits.)

A potentially less technical method for finding that bound is to graph $d 9^5$ and $10^{d-1}$ and find their intersection. The first is a line and the second is an exponential. There will be (at most) two intersections on $d > 0$ and we only care about the larger one (i.e., the one to the right). (Behind the scenes: plot this over a wide enough range of $d$ that you are sure you have included the intersection, then zoom in a bit. Below we show zooming in twice.)

Mathematica graphics

The intersection is between $d = 6$ and $d = 8$. And we check: to the right of that intersection the line is below the exponential, which is the inequality for impossibility of a positive integer equalling the sum of the fifth powers of its digits.

Mathematica graphics

Now we see the intersection is between $d = 6.5$ and $d = 7$.

Mathematica graphics

Now we see the intersection is a bit below $d = 6.6$, which is compatible with the exact result found above. Then $10^{6.6} - 1 = 3\,981\,070.705{\dots}$. So this method gets us within $90\,000$ of the exact cutoff.

For any choice of $k$, you can use the graphical method to bound $d$ and then obtain an upper bound on $N$. But perhaps you don't want to perform this graphical search for every possible $k$.

Notice that $d 9^k < d 10^k$ for $k > 1$ (and we can handle the $k = 1$ case by either method above. We would find that there is no solution when $d > 2.319{\dots}$, so when $N > 207.7{\dots}$). Then if $$ d 10^k < 10^{d-1} $$ it is impossible that $N$ can equal the sum of the $k^\text{th}$ powers of its digits. This is equivalent to $$ 10^{k+1} < \frac{10^{d}}{d} \text{.} $$ Since $d \geq 1$, $\frac{10^{d}}{d} < 10^{d}$ and by monotonicity of $f(x) = 10^x$, we have $k+1 < d$. So we get the (somewhat sloppy) bound $d \geq k+2$, so for positive integer $N$ to be equal to the $k^\text{th}$ powers of its digits, $N < 10^{k+2}-1$.

Eric Towers
  • 67,037