It is known (Senge and Straus, 1971, see also C.L.Stewart, 1980) that for every natural $a$, not a power of 10, and every natural $s$, there are only finitely many $k$ such that the sum of decimal digits of $a^k$ does not exceed $s$. So let $f(s)$ be the largest $k$ with this property. What is the growth rate of $f$? In particular, is it always at most linear? 


Update 1: Conjecture. $\liminf S_{10}(a^k)/k > \log_2(a)$. This would imply that $f$ is bounded by a linear function. Here $S_{10}(u)$ is the sum of decimal digits of $u$.



Update 2: As far as I know the best proved estimate of $f$ is double exponential (C.L. Stewart).