At 2:52 AM -0500 12/12/07, Dan Asimov wrote:
So: suppose each prime 2,3,5,7,...,p_k < sqrt(n) does not divide n while there remain primes p_r in the range p_k < p_r <= sqrt(n).
The greater such k, the greater the chance that such p_r | n.
But also the greater such k, the greater is the chance that n is prime.
How do these two possibilities relate to each other? (I.e., what should I expect, or bet on, as k increases -- that n is prime, or that some larger test prime <= sqrt(n) divides n ???)
"The greater such k, the greater is the chance that n is prime" is correct. "The greater such k, the greater the chance that such p_r | n" needs to be stated more carefully in order to be correct. From the context, one guess at how to state it more carefully is: Conjecture 1: Let f(p_r, k) be the probability that p_r | n, conditional on n being composite and n is not divisible by any prime less than or equal to p_k. Then f(p_r, k) increases with k. But I'm not sure this was what you were trying to express. Then again, it seems like the prime number theorem could not hold if instead it were the case that: Conjecture 2: Let f(p_r, k) be the probability that p_r | n, conditional on n is not divisible by any prime less than or equal to p_k. Then f(p_r, k) increases with k. Paul