Getting Prime by Changing 2 Digits

Question

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$?

Answer 1

This is heuristic argument, not a proof, but too long for a comment.

I believe the conjecture is false. Instead:

Conjecture: The exceptions among even numbers have positive density of $\exp(-90/\log 10) \approx 1.1\times 10^{-17}$, and the smallest exception has around 17 digits.

Let $x$ be an even number with $n$ digits. In order to find a prime by changing two digits we obviously must change the last digit to one of $\{1,3,7,9\}$. To change a second digit, we have $n-1$ choices for a digit to change, and in each place we have $9$ possible replacements, so we have $36(n-1)$ numbers to check for primality, which I will call $x$'s digital varianets. If we say $x = a\cdot 10^{n-1} + \overline{x} + b$, where $a$ and $b$ are digits and $\overline{x}$ is a multiple of 10 with $n-2$ digits, thus the digital variants of $x$ are all in the range of $\overline{x} + 1$ to $9\cdot 10^{n-1} + \overline{x} + 9$. The number of primes in that range is asymptotically $$ \frac{9\cdot 10^{n-1} + \overline{x} + 9}{\log(9\cdot 10^{n-1} + \overline{x} + 9)} - \frac{\overline{x} + 1}{\log(\overline{x} + 1)} $$ Now the heuristic part: We suppose these primes are uniformly randomly distributed in the interval $[\overline{x} + 1, 9\cdot 10^{n-1} + \overline{x} + 9]$. According to this heuristic, the probability of an arbitrary number (which is not a multiple of $2$ or $5$) in this interval being prime is $$ p(x) = \frac{\frac{9\cdot 10^{n-1} + \overline{x} + 9}{\log(9\cdot 10^{n-1} + \overline{x} + 9)} - \frac{\overline{x} + 1}{\log(\overline{x} + 1)}}{(9\cdot 10^{n-1} + 8)(1-\frac12)(1-\frac15)} $$ We have that $\overline{x} = r10^{n-1}$ for some $r\in[0,1)$, and thus we can simplify \begin{eqnarray} p(x) &=& \frac{\frac{9\cdot 10^{n-1} + r 10^{n-1} + 9}{\log(9\cdot 10^{n-1} + r 10^{n-1} + 9)} - \frac{r 10^{n-1} + 1}{\log(r 10^{n-1} + 1)}}{(9\cdot 10^{n-1} + 8)(1-\frac12)(1-\frac15)}\\ &=&\frac{\frac{9+r+\frac{9}{10^{n-1}}}{(n-1)\log 10 + \log(9+r + \frac 9{10^{n-1}})}-\frac{r+\frac{1}{10^{n-1}}}{(n-1)\log 10 + \log(r + \frac 1{10^{n-1}})}}{(9+\frac 8 {10^{n-1}})(1-\frac12)(1-\frac15)}\\ &=& \frac{\frac{9+r}{(n-1)\log 10 + \log(9+r)}-\frac{r}{(n-1)\log 10 + \log(r)}}{18/5} + O(10^{-n})\\ &=& \frac{5}{2\log(10)(n-1)} + O(n^{-2}) \end{eqnarray} Thus we get that the probability that all digital variants of $x$ are composite is \begin{eqnarray} (1-p(x))^{36\cdot(n-1)} &=& \left(1-\frac{5}{2\log(10)(n-1)} + O(n^{-2})\right)^{36(n-1)} = \exp\left(-\frac{90}{\log 10}\right) + O(\frac1n)\\ &\approx& 1.06\times 10^{-17} + O(\frac1n) \end{eqnarray} so, barring some strange coincidences in the pattern of primes, the density of exceptions among even numbers is $\exp(-90/\log 10)$. If all numbers have this probability of being an exception, then the expected smallest exception would be $$\exp(90/\log 10) \approx 9.4 \times 10^{16}$$

---

Addendum: The same heuristic reasoning also leads to the following conjectures:

Conjecture 1: On average, an even number can be made into a prime by changing at most two digits in $\frac{90}{\log 10} \approx 39.087$ different ways.

Conjecture 2: For $k\ge 3$, the set of integers which cannot be made prime by changing $k$ digits is finite (maybe empty).

Here's some numerical evidence to bolster our heuristic: According to the heuristic, the probability that an $n$-digit number has $k$ prime digital variants is approximately $$ \binom{36(n-1)}{k}\left(\frac5{2(\log 10)(n-1)}\right)^k\left(1-\frac5{2(\log 10)(n-1)}\right)^{36(n-1) - k} $$ Taking the limit as $n$ goes to infinity, this becomes a Poisson distribution with $\lambda = \frac{90}{\log 10}\approx 39.087$. Here's a histogram of the number prime digital variants of a random sample 10000 of 10-digit even numbers, along with the conjectured limiting Poisson pdf ($\times 10000$): It looks pretty close, but a little heavier on the upper tail than the Poisson. The mean is of the sample is 40.4, which again is a little bigger than the predicted limiting mean of 39.1. Not bad though, considering this is at $n=10$ when we are expecting a deviation of $O(1/n)$. The values at the extremes may be interesting: The minimum from this sample was 16, hence the closest 10-digit number I found to being a counterexample is 2292915856, which has only 16 digital variant primes:

2092915859, 2492915857, 2892915853, 2202915851, 2202915857, 2202915859 2242915853, 2294915851, 2292015857, 2292913859, 2292918853, 2292918857 2292915151, 2292915353, 2292915557, and 2292915959

On the other extreme, I found two numbers that can be made into primes in 73 different ways by changing up to 2 digits, namely 1585430236 and 9103078842.

Answer 2

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.