[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 (*) ? 2. If not, are the lengths of such sequences unbounded? 3. If not, what's the length of the longest sequence? And: How do the answers to the above questions depend on p ? (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.) But to start with, I'm most interested in the original question for p = 2. --Dan A.
If I may try to rephrase a question: Consider sequences S(p,q_0) = q_0, q_1, q_2, ..., where q_(n+1) = p*(q_n)+1. 1. Do there exist a prime p and number q_0, such that all elements of S(p,q_0) are prime? 2. For any M, do there exist a prime p and number q_0, such that the first M elements of S(p,q_0) are prime? (I think that's what Dan asks.) For (1), I suspect not. Consider any prime element q_k greater than p: Modulo q_k, the sequence is periodic, has 0 in the k'th position, and so will eventually have another zero. There, the original sequence has a multiple of q_k, but not q_k itself. A period of S modulo prime q_k is the order of p in q_k's multiplicative group. p and (p-1) are coprime to q_k because q_k>p. Let r=1/(p-1) mod q_k. Then the sequence S(p,q_0)+r (r+q_0, r+q_1, r+q_2, ...) is purely multiplicative: r+q_(n+1) = p*(r+q_n), and r+q_n = p^n*(r+q_0). So S+r (modulo q_k) has a period equal to p's order, and so does S, and its fundamental period is a factor of that. (Does anyone know which factor?) For (2), I can only speculate: q_0 limits the number of consecutive primes; but maybe we can beat any particular M, by choosing a sufficiently large q_0. -- Don Reble djr@nk.ca
----- 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.
participants (3)
-
asimovd＠aol.com -
David Wilson -
Don Reble