6

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)

Hippalectryon
  • 7,730
  • Indeed, you can always take $n=2$. Adapt the proof shown, e.g., here: http://math.stackexchange.com/questions/417486/probability-that-the-first-digit-of-2n-is-1 – lulu Sep 02 '15 at 15:46
  • 2
    In other words, given $a$, you want to find $n$ such that $$a\cdot10^k \leq n^a < ( a + 1 )\cdot 10^k$$ for some $k$. It seems to me that, taking $k$ really large, one should expect to find some $a$-th power in the corresponding range. – Blue Sep 02 '15 at 15:47
  • 2
    @Blue. Indeed you can, so long as $n$ is not a power of $10$ anyway. Look at the map which takes a positive number $x$ to the fractional part of $log_{10}(x)$. That's a map to the circle and multiplication by $n$ becomes addition with $log_{10}(n)$. Unless $n$ is a power of $10$ this is the same as a rotation by an irrational angle, hence iterating this map gives a dense subset of the circle. – lulu Sep 02 '15 at 16:04
  • Is it even computable without keeping all digits in memory? – mathreadler Sep 02 '15 at 19:06
  • 1
    $4017382^{2004}$ begins with $2004$. That number has 13,235 digits. – Akiva Weinberger Sep 02 '15 at 19:41
  • @columbus8myhw Can you share your algorithm (pastebin,...) ? Thanks :-) – Hippalectryon Sep 02 '15 at 20:06
  • I just messed around with Wolfram Alpha. Solving for $m_k$ in Wofsey's answer, I found out that it had to be at least $4017018$. So I tried $4017500$, which turned out to be too large. Then I tried $4017300$, which was too small. Etc. – Akiva Weinberger Sep 02 '15 at 20:28

2 Answers2

4

Yes, this is always possible. As stated in the comments, you are looking for an $n\in\mathbb{N}$ such that $a\cdot 10^k\leq n^a<(a+1)\cdot 10^k$ for some $k\in\mathbb{N}$. For any $k$, let $m_k$ be the largest integer such that $m_k^a< a\cdot 10^k$. Then $(m_k+1)^a\geq a\cdot 10^k$, and $(m_k+1)^a<(a+1)\cdot 10^k$ as long as $$\left(\frac{m_k+1}{m_k}\right)^a\leq\frac{a+1}{a}.$$ This last inequality is true as long as $m_k$ is sufficiently large, since the left-hand side converges to $1$ as $m_k\to \infty$. But $m_k\to\infty$ as $k\to\infty$, so this inequality must hold for all sufficiently large $k$. Thus $n=m_k+1$ is a number of the sort you seek for all sufficiently large $k$.

Eric Wofsey
  • 330,363
2

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

r.e.s.
  • 14,371