Getting Prime by Changing 2 Digits I just got a result that one cannot get a prime from arbitrary natural number $n$ by changing only one digit of its decimal expansion. For example, you cannot get prime by changing only one digit of $200$ since you need to change the last digit. Another proof is one can use prime number theorem by assuming we can change only one digit of $10k, k\in \mathbb{N}$ to get prime, but this means
\begin{align*}
\pi(x)\geq \sum_{k\leq x/10}1\geq \lfloor x/10 \rfloor
\end{align*}
which contradicts prime number theorem. My question is, can we get prime by changing exactly two digits of $n$ for arbitrary $n \geq 100$?
 A: Let b be a neighbour of a if the number of digits is the same, the last digit of b is 1, and exactly one other digit is different. Since we cannot change the first digit to 0, an n digit integer has (n-1)*9-1 = 9n - 10 neighbours. The (false) hypothesis is that every integer >= 10 has a prime neighbour.
An arbitrary integer x is statistically prime with probability 1 / ln x. Integers ending in 1 are not divisible by 2 or 5. 40% of integers are not divisible by 2 or 5, but contain all the primes. We conclude that a random x ending in 1 is a prime with probability 2.5 / x. A random n digit integer has a logarithm from (n-1) ln 10 to n ln 10, so a random n digit integer ending in 1 is prime with probability (2.5 / ln 10) / (n - 1 to n).
An n-digit integer has (9n - 10)(2.5 / ln 10) / (n-1 to n) prime neighbours on average, which is (9-10/n)(2.5 / ln 10) multiplied by a factor from 1 to 1 + 1 / (n-1). This is very close to the constant 9 * (2.5 / ln 10) ≈ 9.77. With this average number of prime neighbours, you can expect very roughly 1 in 17,500 numbers to have no prime neighbour.
We change the definition slightly: b is a neighbour if it ends in 1, 3, 7 or 9. This means four times as many numbers, which means roughly 39.08 prime neighbours on average, so about one in 9 x 10^16 numbers have no prime neighbour. This could be estimated slightly better. This is enough that infinitely many counter examples can be found, yet rare enough that finding one counter example will be hard work and might be missed. (But if we counted the number of neighbour primes, we would find several with one or two prime neighbours to make us suspect that the hypothesis is false).
Now the real definition: b is a neighbour if exactly two digits are different. If x ends in 1, 3, 7 or 9, then we have about (9n-10)^2 / 2 neighbours ending in 1, 3, 7 or 9 and therefore more likely than average to be prime. We expect very roughly 40n prime neighbours. The existence of a large number with no prime neighbours is not impossible but highly unlikely.
If x doesn’t end in 1, 3, 7 or 9 then we are exactly back at the second case, because one of the two changes must be changing the LG last digit to 1, 2, 7, or 9.
So the whole hypothesis is false, but with huge distances between counter examples. The average number of counter examples <= N will converge to a very small constant. This is how you would get a false hypothesis, except we can have “almost” counterexamples that are much more common, and with enough “almost” counter examples we wouldn’t think no counter examples exist.
