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.]

 Terence Tao on Polymath15, ninth thread: goin… Anonymous on Polymath15, ninth thread: goin… KM on Polymath15, ninth thread: goin… Anonymous on Polymath15, ninth thread: goin… “The beauty of… on Maryam Mirzakhani A short proof of the… on 245A, Notes 5: Differentiation… I think my mathemati… on There’s more to mathematics th… masoudkomi on Books Terence Tao on Tricks Wiki article: The tenso… Paulin Ndoj on Does one have to be a genius t… Anonymous on Polymath15, ninth thread: goin… Anonymous on Which universities should one… Anonymous on Polymath15, ninth thread: goin… Anonymous on The theorems of Frobenius and… Vivek Sharma on 246C notes 3: Univalent functi…