(This question is inspired by the StackOverflow question Converting prime numbers by @Manas, which turns out to be the problem PPATH
of SPOJ.)
Let's construct a graph $G$ of all primes $p$ having $L$ digits in base-$n$. Two primes $p$ and $q$ form an edge in $G$ iff they only differ in $1$ digit (e.g. $1\mathbf{0}09$ and $1\mathbf{1}09$ form an edge).
Is there some (approximated?) condition on $n$ and $L$ that $G$ is connected?
For example, it seems that when $n$ is odd $G$ is usually disconnected, while when $n$ is even ($>2$) $G$ is usually connected.