----- Original Message ----- From: <asimovd@aol.com> To: <math-fun@mailman.xmission.com> Sent: Thursday, February 27, 2003 11:03 PM Subject: [math-fun] (Another) Prime Question:
<< First, what about other bases besides ten? [This is normally dan asimov's question, isn't it?]
I must express my gratitude for someone's finally taking the burden off me in this case (:-)>.
In fact I was thinking of related questions that aren't directly base-related. Here's one:
For any prime p consider the mapping f_p : N -> N given by f_p(n) = p*n + 1.
Consider (possibly finite) sequences of primes
(*) q_0, q_1, q_2, ..., where q_(n+1) = f_p(q_n) for n = 0,1,2,...
Given prime p fixed: 1. Is there an infinite prime sequence (*) ?
If p is odd, every other term of {q(n)} will be even, which means that the sequence includes at most 2 consecutive primes (these would be a(0) = 2 and a(1) = 2p+1). To get long runs of primes, you want to choose p even, not prime. Therefore I will drop the assumption that p is prime for the remainder of this discussion. But even if p is even, {q(n)} will never consist of all primes. Suppose {q(n)} is a sequence of primes. Let m = q(1), m will be a prime different from p. You can then show that r(n) = q(n) mod m is a cyclic function of n with period w <= m-1. Since r(1) = q(1) mod m = q(1) mod q(1) = 0, we must have r(kw+1) = 0 for k >= 0. This means q(kw+1) mod m = 0 and m divides every w-h element of {q(n)} starting at q(1). Since {q(n)} is increasing, we will have q(kw+1) will be composite with divisor m for k >= 1. Thus there can be at most w+1 <= m consecutive primes in {q(n)}, these would be q(0) through a(w), where q(0) = p, q(1) = m.
2. If not, are the lengths of such sequences unbounded?
Given even p, by judicious choice of q(0), you can eliminate any set of primes as possible divisors of any q(n). Specifically, you can eliminate all primes <= p, in which case you open up the possibility of nextprime(p)-1 consecutive primes in {q(n)}. However, {q(n)} grows exponentially, and larger elements will tend to have spurious large prime divisors, which means that you are unlikely to find a maximal run of consecutive primes if p is even moderately large (the problems are the same as with searching for consecutive primes in arithmetic progression).
3. If not, what's the length of the longest sequence?
There is no a priori longest sequence.
And: How do the answers to the above questions depend on p ?
See (2) The value of p by itself does not limit the possible number of consecutive primes in {q(n)}.
(Variants: one could look at g_p(n) = p*n - 1, or allowing +-1 at each iteration, or even allow any of the f_p's (or g_p's) to be applied at any stage in the iteration.)
Don't hurt my head.
But to start with, I'm most interested in the original question for p = 2.
In this case, let p be an odd prime and let q(0) = p# / 2 - 1. This will give you the possibility of nextPrime(p)-2 consecutive prime elements in {q(n)}.
--Dan A.