Re the suggestion by RCS that "the stats become much more favorable if one considers changing TWO digits"... we ask... QUESTION: Does there exist an integer K>0 such that all primes (except perhaps for a finite set of exceptions) are "connected" where two primes are called connected if they differ in K or fewer digit locations? HEURISTIC ANSWER: The number of D-digit primes is about 10^D / (D*ln(10)) and the number of "neighbor numbers" connected to a given such prime, is 9^K * (D choose K) if all K digits change (plus some lower order terms if fewer than all K change). The "expected number" of those neighbors that are prime is about 9^K * (D choose K) / (D*ln10). The chance that all neighbors are nonprime is about exp( -9^K * (D choose K) / (D*ln10) ). The expected number of D-digit "isolanis" (primes lacking prime neighbors) is thus about exp( -9^K * (D choose K) / (D*ln10) ) * 9^K * (D choose K) / (D*ln10). We now sum this over all D=1,2,3... and observe that the result is finite if K>=2. If K=1 then the sum is infinite similarly to SUM(1), If K=2 then the sum is finite similarly to SUM(D*exp(-D)). Of course the heuristic reasoning above should be altered by inserting various constant fudge factors in various places, but it will not be enough to alter these finiteness/not results. Now you can also consider, not merely "isolanis" which are singleton connected components, but also connected componets containing C primes, for C=1,2,3,4,... and sum over C. This does not alter the conclusion. So: I would conjecture that if we call two primes 'connected' when they differ in 2 or fewer digits, then: all besides a finite set of exceptional primes are connected. (And this is also true in any radix>=2.)