mersenneforum.org Factor tree questions
 Register FAQ Search Today's Posts Mark Forums Read

 2017-10-14, 01:47 #1 ThomRuley     May 2003 23×31 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
2017-10-14, 02:10   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by ThomRuley 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
http://www.lirmm.fr/~ochem/opn/ links to the paper I think you are reading, and gives one example, that I can't quite get my head around.

 2017-10-14, 02:23 #3 ThomRuley     May 2003 23·31 Posts I'm pretty sure I'm missing something too. That's why I was hoping someone could maybe explain it a different way.
2017-10-14, 14:58   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by ThomRuley I'm pretty sure I'm missing something too. That's why I was hoping someone could maybe explain it a different way.
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 2017-10-14 at 15:45

 2017-10-14, 20:05 #5 Pascal Ochem     Apr 2006 103 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.
2017-10-14, 20:56   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by Pascal Ochem 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

 2017-10-14, 22:12 #7 Pascal Ochem     Apr 2006 103 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 ?
2017-10-14, 22:19   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Pascal Ochem 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 ?
it's on that page I link to in post 2 in the example.

 2017-10-14, 23:42 #9 Pascal Ochem     Apr 2006 103 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.
2017-10-15, 19:34   #10
ThomRuley

May 2003

23×31 Posts

Quote:
 Originally Posted by Pascal Ochem 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.
Let k be the number of distinct prime factors of an OPN.
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?

 2017-10-16, 16:56 #11 Pascal Ochem     Apr 2006 103 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 2017-10-16 at 16:57

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow Aliquot Sequences 11 2016-11-02 05:05 houding Information & Answers 16 2015-08-01 10:47 VJS Prime Sierpinski Project 17 2010-03-14 10:08 dsouza123 Software 12 2003-08-21 18:38 Axel Fox Lone Mersenne Hunters 3 2003-05-27 13:52

All times are UTC. The time now is 00:20.

Fri Oct 22 00:20:28 UTC 2021 up 90 days, 18:49, 2 users, load averages: 1.63, 1.43, 1.33