It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it.
But the powers of 2 represented in ternary appears to be non regular. Pumping lemma or residue classes is hard to apply as there seems to be very little pattern among the strings. How do I solve it?
In general, for what powers of $k$ represented in base $r$, is the set regular?
Here's an alternative solution (with detailed explanation) using Myhill-Nerode Theorem. I'll use base $3$ and $2$ for readibility, but the proof generalizes for arbitrary bases $r,k$ that are not powers of the same integer.
(1) Show that given any ternary string $x$, there exists another string $y$ such that $xy$ is a power of $2$.
Proof: Given any $x$ (letting $n$ be the number it represents), $\forall k$ and $c\in \{0,\ldots,3^k-1 \}$, there exists $y$ such that $xy$ represents $3^kn + c$. In fact, this characterizes all the numbers $xy$ can represent. Hence, finding the minimal $y$ such that $xy$ is a power of $2$ is depends on finding the smallest integer $k$ such that we have some power of $2$ in the interval $[3^kn,3^k(n+1)-1]$. Taking log base $2$, we need to find $k$ such that we have an integer in the interval $[k\log 3 + \log x, k\log3 + \log(x+1)]$ (dropping the $-1$ here is iffy, but simplifies calculations which do not rely on it). Notice that changing $k$ only affects the $k\log 3$ portion, so we can find a $k$ that gets us arbitrarily close to some integer.
(2) Given some $x$ and the corresponding minimal $y$, show that there exists a string x' such that the corresponding minimal $y'$ has to be larger than $y$. Repeating this gives us infinitely many equivalence classes of strings.
Proof Outline: Since $\log 2^m x = m + \log x$, given an $x$ and its corresponding $y$ and $k$ we can always find some $x' = 2^m x$ where $\log(2^m x + 1) - \log (2^m x)$ is sufficiently tiny such that no integer is contained in $[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$. Note that we are implicitly using the fact that $k\log 3 + \log x$ can never be an integer.
In general, for what powers of $k$ represented in base $r$, is the set regular?
Your question is a subcase of Cobham's Theorem (Alan Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Theory of Computing Systems 3(2):186--192, 1969, doi: 10.1007/BF01746527):
Let $S$ be a set of non-negative integers and let $m$ and $n$ be multiplicatively independent positive integers. Then $S$ is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is ultimately periodic
Here by multiplicatively independent one means there does not exist non-zero $p$ and $q$ such that $m^p=n^q$. Cobham cites Büchi for your specific case of powers of some $k$ in base $r$, which is recognizable only if $k$ and $r$ are multiplicatively dependent.
If you are interested in this result, there is a rather nice survey by Véronique Bruyère, Georges Hansel, Christian Michaux, and Roger Villemaire (Logic and $p$-recognizable sets of integers, Bulletin of the Belgian Mathematical Society 1(2), 1994, PDF), which also shows the relationship with Presburger arithmetic.
The pumping lemma implies that there is a sequence like $x_n = c+b(r^{dn}-1)/(r^d-1)$ for some $b,c,d$ such that each $x_n$ is a power of $k$. So $\log_k(x_n)=dn \log_k(r) + const + o(1)$ is always an integer, so $\log_k(r)$ is rational.
Here's an explanation of that formula for $x_n$. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is a power of $k$. Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, $x_n = u r^{dn+e} + v r^{d(n-1)+e} + v r^{d(n-2)+e} + \dotsb + v r^e + w$ is a power of $d$. So $x_n-x_{n-1} = (u r^d - u + v) r^{d(n-1)+e}$. Writing $b=(u r^d - u + v)r^e$ and $c=x_0-b$ we have $x_n=c+b(r^{dn}-1)/(r^d-1)$.
Let $L$ be the set of powers of 2 encoded in base 3. The encoding of $4^n$ in base 3 ends with 1, whereas the encoding of $2\cdot 4^n$ in base 3 ends with 2. Hence $L' = L \cap \Sigma^*1$ is the encoding of all powers of 4.
The encoding of an integer $m > 0$ in base 3 takes $\lceil \log_3 (m+1) \rceil$ digits. Since neither $4^n$ nor $4^n+1$ are powers of 3 for $n>0$ (since neither is divisible by 3), the encoding of $4^n$ takes $\lfloor \log_3 4^n \rfloor + 1$ digits.
Let $N = \{ \lfloor \log_3 4^n \rfloor : n \geq 0 \}$ (this is a Beatty sequence). Suppose that $L$ were regular. Then so would $L'$ be. This implies that the set of lengths of words in $L'$ is eventually periodic, and so $N$ is eventually periodic. In particular, $N$ would have rational asymptotic density. However, $N$ has asymptotic density $1/\log_3 4$, which is irrational.
