mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-10-14, 01:47   #1
ThomRuley
 
ThomRuley's Avatar
 
May 2003

13·19 Posts
Default 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
ThomRuley is offline   Reply With Quote
Old 2017-10-14, 02:10   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-10-14, 02:23   #3
ThomRuley
 
ThomRuley's Avatar
 
May 2003

13·19 Posts
Default

I'm pretty sure I'm missing something too. That's why I was hoping someone could maybe explain it a different way.
ThomRuley is offline   Reply With Quote
Old 2017-10-14, 14:58   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-10-14, 20:05   #5
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

97 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
Old 2017-10-14, 20:56   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
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
Old 2017-10-14, 22:12   #7
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

1418 Posts
Default

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 ?
Pascal Ochem is offline   Reply With Quote
Old 2017-10-14, 22:19   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-10-14, 23:42   #9
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

6116 Posts
Default

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.
Pascal Ochem is offline   Reply With Quote
Old 2017-10-15, 19:34   #10
ThomRuley
 
ThomRuley's Avatar
 
May 2003

13×19 Posts
Default

Quote:
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.
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?
ThomRuley is offline   Reply With Quote
Old 2017-10-16, 16:56   #11
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

1418 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is there a copy of "the" aliquot tree anywhere? Dubslow Aliquot Sequences 11 2016-11-02 05:05
ECM questions houding Information & Answers 16 2015-08-01 10:47
llr 3.8 questions VJS Prime Sierpinski Project 17 2010-03-14 10:08
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38
2 little questions Axel Fox Lone Mersenne Hunters 3 2003-05-27 13:52

All times are UTC. The time now is 22:56.

Thu Mar 4 22:56:17 UTC 2021 up 91 days, 19:07, 0 users, load averages: 1.90, 1.68, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.