Riddle : Given an integer power, does any integer to this power start with the power? I initially found the following riddle somewhere : Is there an integer $n$ such that $n^{2004}$ starts (from the left) by $2004$ ?
I was unable to find an answer, but I found the question rather interesting and couldn't find any such question on MSE, hence I'm wondering :
Given a non trivial positive integer $a$, when is there a positive integer $n$ such that $n^a$ starts by $a$ ?
(By trivial integers I mean cases like $a=1,a=2,\dots$ etc for which $n$ can very easily be found)

This is a special case of the following theorem (Lemma 2.1 in this paper on disjunctive sequences), whose proof is along the same lines as that posted in the answer by @EricWofsey:

If $a_1, a_2, a_3, \dots$ is a strictly increasing infinite sequence
  of positive integers such that $$\lim_{n\to \infty}
\frac{a_{n+1}}{a_n} = 1$$ then for any positive integer $m$ and any
  integer base $b \ge 2$, there is an $a_n$ whose expression in base $b$
  starts with the expression of $m$ in base $b$.

Your result is then the very special case of taking $a_n = n^k$ and $k=m$. For this and some other special cases, see these examples of disjunctive sequences. (E.g., for any desired positive integer, there are infinitely many prime numbers whose representation begins with the digits of that number.) 
NB: For any positive integer exponent $k$ and any desired positive integer $m$, there are infinitely many positive integers $n$ such that the representation of $n^k$ starts with the representation of $m$; furthermore, this holds for digital representations in any integer base $b \ge 2$. 
