Integers $n$ for which the digit sum of $n$ exceeds the digit sum of $n^5$

Solution 1:

Such formulas for such numbers exist for all even $k$. The formula is not as magical as it seems. Consider

$$ 10^{ni}-m\sum_{s=0}^{n-1}10^{si}\;. $$

with fixed $m,n$ for all $i$. There are $n$ stretches of $O(i)$ nines in this number. Taking it to the $k$-th power yields

$$ \left(10^{ni}-m10^{(n-1)i}\right)^k+R\quad\text{with}\quad R\in o\left(10^{k(n-1)i}\right)\;. $$

For even $k$, the terms with the highest powers of $m$ in the remainder $R$ are all positive, so by making $m$ large enough, we can make all terms in $R$ positive. Then we only have $k/2$ negative terms in the leading power, and hence only $k/2$ stretches of $O(i)$ nines, and all other stretches of $O(i)$ repeating digits are zeros. The remaining constant digits contribute $O(1)$ to the digit sum, so for $n\gt k/2$ the larger number of $O(i)$ stretches of nines wins out for sufficient $i$.

Unfortunately this doesn't work for odd $k$, since $R$ then contains a mixture of signs. Nevertheless, one could systematically search for such formulas using the ansatz

$$ \sum_{s=0}^nc_s10^{si}\;, $$

expanding the $k$-th power and solving the linear program resulting from requiring that only a small number of terms are negative.