



Heuristically, a random n-bit integer has roughly a 1/n chance (up to multiplicative constants such as \log 2) of being prime. So amongst the 2n numbers p \pm 2^i for 0 \leq i < n-1 and a fixed prime p, one expects about O(1) of these numbers to be prime on the average. A more refined calculation (using the Hardy-Littlewood prime tuples conjecture) suggests that the expected number of primes exceeds 1 (in fact it should be asymptotically 2 \Pi_2 / \log_2 2 \approx 3.8096\ldots, where \Pi_2 := 2 \prod_{p > 2} (1 - \frac{1}{(p-1)^2}) is the twin prime constant), which means that the main result is unlikely to be established purely by the first moment method. Fortunately, a little bit of elementary sieving using, of all things, the prime factors of Mersenne numbers, allows one to manipulate the expected number of primes to be significantly less than 1, to the point where standard upper bound sieves (in particular, the Selberg sieve) give satisfactory results.

It is nice for a change to write an elementary paper of six eight pages in length; the only moderately advanced tools I use here are the prime number theorem in arithmetic progressions, and the standard upper bound from the Selberg sieve for any two-dimensional sieving problem (in which one is allowed to eliminate up to two residue classes mod q for every prime q).

[Update, Feb 25: It has been pointed out to me that the base 2 result was implicitly obtained by Cohen and Selfridge, and explicitly pointed out by Sun, using the covering congruence method of Erdős, so I have rewritten the paper to focus primarily on the case of general bases (to which it is not entirely clear that a set of covering congruences exists). The earlier version (which focused only on the base 2 case, and so is slightly simpler) can be found here.]

[Update, Feb 26: It should now also be possible to prove the following generalisation: for any base a and any r, there should exist infinitely many primes which become composite whenever one changes one of the digits, and also appends or deletes up to r of digits on either end of the digit expansion. My method comes very close to establishing this result, except for one annoying issue arising from the fact that numbers such as j a^i + l (with j, l = O(1)) can occasionally have a huge number of prime factors. This seems to be a rare event, though, so presumably one should be able to modify the argument to obtain this result. I'll leave this for someone else to try, though. One should also be similarly able to replace "change one of the digits" to "delete or insert a digit at an arbitrary location".]