Thread: Factor tree questions View Single Post
 2017-10-14, 20:05 #5 Pascal Ochem     Apr 2006 101 Posts Suppose N has no small factor. Say small is less than 1000. Then every prime factor contributes to at most 1.001 to the abundancy. Since 1.001^693 < 2, N has at least 694 prime factors. So N > 1000^ 694 > 10^2082. This argument can be improved but the general idea is this: if we can forbid small prime factors, we get a good lower bound. "Forbidding a prime p" means this: We suppose both that N is less than a bound B and that p divides N. Then the role of the tree is to obtain a contradiction. After that, p is forbidden, that is, we know that if N < B, then p does not divide N. So we forbid enough small primes until the argument above works. Why is there a strange order on the list of forbidden primes ? Why don't we just forbid first 3, then 5, 7, 11, and so on ? This is because forbidding a prime p has a second advantage: once p is forbidden, you can cut the branches of subsequent trees when p appears. For example, we forbid 19 before 7 because sigma(7^2)=3*19, thus, in the tree of 7, the subtree corresponding to 7^2 is immediately cut. We forbid 11 early on because it appears relatively often: Every branching of the form p^4 has probability 0.4 of producing a factor 11. On the contrary, 17 must be forbidden because it is a rather small prime, but 17 is not very good at cutting branches (probability 1/16 of producing a factor 17 only for components of the form p^16). By putting 17 is at the end of the list, we ensure that the tree for 17 will be small because of all the previous primes in the list that have been ruled out . If it is still not clear, if you have other questions, please ask.