View Single Post
Old 2017-10-14, 20:05   #5
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

101 Posts
Default

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.
Pascal Ochem is offline   Reply With Quote