You are currently browsing the tag archive for the ‘primes’ tag.

I’ve just uploaded to the arXiv the short note “A remark on primality testing and the binary expansion“, submitted to the Journal of the Australian Mathematical Society. In this note I establish the following result: for any sufficiently large integer n, there exists an n-bit prime p, such that the numbers $p \pm 2^i$ for $i=0,\ldots,n-1$ are all composite. In particular, if one flips any one of the bits in the binary expansion of the prime p, one obtains a composite number. As a consequence, one obtains the (rather plausible) consequence that in order to (deterministically) test whether an n-bit integer is prime or not, one needs (in the worst-case) to read all n bits of the prime. (This question was posed to me by my colleague here at UCLA, Yiannis Moschovakis.)

Primes p of the form mentioned in the above result are somewhat rare at first; the first some prime is $1973 = 11110110101_2$. But in fact, the argument in my note shows that the set of such primes actually has positive relative density inside the set of all primes. (Amusingly, this means that one can apply a theorem of Ben Green and myself and conclude that there are arbitrarily long arithmetic progressions of such primes, although I doubt that there is any particular significance or application to this conclusion.)

The same remark applies to other bases; thus, for instance, there exist infinitely many prime numbers with the property that if one changes any one of the base 10 digits of that number, one obtains a composite number. (Presumably the first such number can be located by computer search, though I did not attempt to do so.) [Update, Feb 25: see comments.]

### Recent Comments

 Anonymous on Open question: scarring for th… Various Items | Not… on IMU Graduate Breakout Fellowsh… Anonymous on Open question: scarring for th… louigiaddario on IMU Graduate Breakout Fellowsh… gninrepoli on P=NP, relativisation, and mult… Wolfgang Arendt on A quick application of the clo… Terence Tao on Ultrafilters, nonstandard anal… sagar on Ultrafilters, nonstandard anal… Anonymous on On time management Terence Tao on An elementary non-commutative… Anonymous on An elementary non-commutative… Nathan on 254A, Notes 1: Concentration o… Terence Tao on Distinguished Lecture Series I… Terence Tao on 254A, Notes 1: Concentration o… Anonymous on Distinguished Lecture Series I…