20171014, 01:47  #1 
May 2003
13·19 Posts 
Factor tree questions
I've been reading a couple of papers lately about the OPN problem. I understand how proof trees work, but I still have a question about the more detailed parts of it. I notice that Brent et al had a list of forbidden factors, as do Ochem and Rao.
Brent et al 127,19,7,11,31,13,3,5 Ochem and Rao 127,19,7,11,331,31,97,61,13,398581,1093,3,5,307,17 I still don't understand why were "forbidden" in the proof trees. Is it similar to Kishore 1983, where an OPN not divisible by 3 has more prime factors? Thanks 
20171014, 02:10  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20171014, 02:23  #3 
May 2003
13·19 Posts 
I'm pretty sure I'm missing something too. That's why I was hoping someone could maybe explain it a different way.

20171014, 14:58  #4 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
If I knew, where the formula's they plug things into came from ( might go read the OPN forum on here ( okay I thought one was here but can't find it)), then I might be able to figure it out. I see where some of the numbers in the formulas seem to come from.
Last fiddled with by science_man_88 on 20171014 at 15:45 
20171014, 20:05  #5 
Apr 2006
97 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. 
20171014, 20:56  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20171014, 22:12  #7 
Apr 2006
141_{8} Posts 
Sure, an OPN with no factor less than a billion has at least 693,147,181 prime factors.
This is the easy part, that I call "end game" on my page. The hard part is the proof that an OPN smaller than B is not divisible by any of the primes in [127,19,7,11,331,31,97,61,13,398581,1093,3,5,307,17]. This hard part is computer intensive because it must explore the large factor trees (in particular the trees for 127, 19, 7, and 11 are large) and it needs a lot of factors of numbers of the form sigma(p^q). What is 1.1671 ? 
20171014, 22:19  #8  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20171014, 23:42  #9 
Apr 2006
61_{16} Posts 
You are referring to circumvention of roadblocks.
This is a different kind of problem. end game: Suppose that N is coprime to 3*5*7*11*13*31. Give a lower bound on N. circumvention of roadblock: Suppose N < 10^2100. Suppose that N is coprime to 127*19. Suppose that 7^378  N and that no prime factor of sigma(7^378). Give an upper bound on the smallest prime divisor of N distinct from 7. I will update the section about circumventing roadblocks since the factors of sigma(2801^82) are now known and I will add more explanations for you to see where the numbers come from. 
20171015, 19:34  #10  
May 2003
13×19 Posts 
Quote:
Since according to Grun 1952, the smallest factor p1 < (2/3)k +2, forbidding all small factors under a certain bound would also result in an increase in k. Perhaps that could be used in a proof increasing the number of distinct prime factors of an OPN. Am I understanding that correctly? 

20171016, 16:56  #11 
Apr 2006
141_{8} Posts 
no, p1 < (2/3)k +2 does not help. It does not say anything in the case of an OPN that is divisible by 3 and some other small primes.
Look at the paper by Pace Nielsen showing that k>=10 https://math.byu.edu/~pace/BestBound_web.pdf In particular, he discusses the kind of obstacle we face if we want to get k>=11. On an unrelated note, Pace's paper has lot more math than our paper for N>10^1500. It is a great result. On the other hand, p1 < (2/3)k +2 is a rather weak result. It is better than our trivial argument above with p1=10^9 and k=693,147,181 which gives p1 < k/ln(2) +constant. But it should be possible to obtain p1 = O(sqrt(k)*ln(k)). Last fiddled with by Pascal Ochem on 20171016 at 16:57 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is there a copy of "the" aliquot tree anywhere?  Dubslow  Aliquot Sequences  11  20161102 05:05 
ECM questions  houding  Information & Answers  16  20150801 10:47 
llr 3.8 questions  VJS  Prime Sierpinski Project  17  20100314 10:08 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 
2 little questions  Axel Fox  Lone Mersenne Hunters  3  20030527 13:52 