3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

I think Terry Tao's paper might help here: http://arxiv.org/abs/0802.3361

It shows that the isolated primes are of positive relative density. I'm not sure if the method can be extended to show that there are large connected blocks.

$\endgroup$
0
$\begingroup$

This question seems fairly advanced. You may want to consider asking it on MathOverflow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.