Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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