From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Primes in exponential sequences (was: Re: Math In Newspapers)
Date: 7 Jan 1998 04:54:34 GMT

In article <68uese$j23$1@news.nevada.edu>,
Troy Kessler <kesslert@nevada.edu> wrote:
>I saw in the book Fermat's Enigma that (10^n-7)/3 is prime for
>n=2,3,4,5,6,7,8. Are there more values of n such that this is prime?

Maple took a couple of minutes to handle this (getting noticeably slower
as  n  increased):

for n from 1 to 200 do if isprime((10^n-7)/3) then print(n):fi: od:

	2, 3, 4, 5, 6, 7, 8, 18, 40, 50, 60, 78, 101, 151

Not to say that there couldn't be some deep pattern here, but it
certainly does appear you're taking a "random" n-digit number and
asking if it's prime. Using the prime number theorem, we can estimate
the number of n-digit primes -- it's about 9/log(10) * 10^(n-1)/n --
and conclude that a randomly selected n-digit number is prime with
probability about  C / n  (where C = 1/log(10)); in fact it'll differ
from   C / n  by at most  C'/n^2. Now select an  n-digit number at
random for each  n = 1, 2, ..., N; what's the expected number of them that
are prime? It's about  C * (1 + 1/2 + ... + 1/N ), and more precisely
it differs from  C * log(N)  by at most  C''/ N. In particular, if you were
to randomly select an  n-digit number  a_n  for each  n, and ask if it were
prime, you would have to be phenomenally  (un)lucky to have only a
finite number of primes in your sequence. 

Precisely the same reason shows why it is reasonable to think there
may be infinitely many Mersenne primes. (Similar reasoning can be
used to suggest there are only finitely many Fermat primes). 

Now, _proving_ these statements about _particular_ sequences is another
matter!

dave

PS: Maple's primality test is a probabilistic one; one must allow for
the possibility that these are "false positives", e.g. (10^101-7)/3 is
not _proven_ to be prime. But it almost surely is, and the rest of
the argument applies regardless.