View Single Post
Old 2017-10-14, 20:56   #6
science_man_88's Avatar
"Forget I exist"
Jul 2009

26×131 Posts

Originally Posted by Pascal Ochem View Post
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.
not sure what the numbers determining the 1.1671 part are or where they appear in your example here for example. because without that your same math as shown here would suggest 10^9 would bring the number of factors to at least 693,147,181
science_man_88 is offline   Reply With Quote