[math-fun] Least prime divisor probabilities (or, The Lurch of the SubGenius)
[*begin discursiveness warning*] In trying to mentally factor a 4-digit number (7989, if you must know). After dividing by the obvious 3, the next step was to find the least prime factor of 7989/3 = 2663. I tried the only factoring algorithm I know: naively try each prime in order no greater than the square root of the number (in this case < 52). I soon realized (what everyone else probably knows well): that if 2663 were not prime, then the more primes that were eliminated, the more likely it became that the next test prime <= sqrt(2663) would divide it. But of course there was always the chance the 2663 is in fact prime. 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 ???) (For starters, let p_r denote the largest prime <= sqrt(n).) [*end discursiveness warning*] --J.R. "Dan" Dobbs
On Wed, 12 Dec 2007, 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.
Isn't that backward? 2 divides 1/2 the integers, 3 divides 1/3 the integers, etc. The lowest primes are the most likely to divide any given int. -J
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
participants (3)
-
Dan Asimov -
Jason -
Paul R. Pudaite