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).

Update 3: Since somebody erased my comments below, I add it here. The problem is related to the exponential Diophantine equation $10^{k_1}+...+10^{k_s}=a^k$. See the book Shorey, T. N.; Tijdeman, R. Exponential Diophantine equations. Cambridge Tracts in Mathematics, 87. Cambridge University Press, Cambridge, 1986.