Contributions came from Steffen Jakob, Jan van Delden, Giovanni Resta.
Q1: Large solutions can be found with less
effort if one uses: DigitSum(v^p)=DigitSum((v*10^k)^p)=v*10^k.
Instead of trying the powers of v*10^k the
numbers can be kept relatively small by searching for v*10^k in
the digit sum of v^p.
I used v=9 because we always have
DigitSum(9^p)=0 mod 9, which hopefully increases our luck.
Solution: 900000^209412 Digits 1246890
Q3: If we assume that the average digit is
4.5 (the digits are uniformly distributed over 0..9), and the
digit sum equals v, we should require v/4.5 digits
The power required can be approximated by
using 9^p=10^(v/4.5), i.e. p*log(9)=v/4.5 hence
p=v/(4.5*log(9)). If we substitute v=9*10^5 we get p about
So the given estimate is not bad at all.
Or more sophisticated: 9^p=4.5*[10^(v/4.5)-1]/9 assuming all
those digits are 4.5 (which is not possible in real life..),
which generates essentially the same p.
The real trick is to calculate an interval
in which p probably lies. Each digit can be described as drawn
from a uniform distribution (*) with mean 4.5 and variance
If we draw n digits the average value of a
digit will follow a normal distribution with mean 4.5 and
variance 99/(12*n), if n is large enough. The variance decreases
rapidly with n.
If n is approx 200000 this would give us an
95% confidence interval for the average digit [4.475,4.525].
Which would give an estimate for p: [208432,210761] <skewed>.
(*) This might not be true, because the
digits are not drawn independently, but calculated using v^p.
However the predictions for v=9*10^k, for k<=5, seem to work
My best result for puzzle 645 is
35900000^3122353 which has 23589672 digits whose sum is 35900000.
I also searched for examples of n^e with d digits such
that n,e, and d are prime numbers.
One such example is 5059937^167677 with 1124131 digits.