Factor tree questions

ThomRuley · 2017-10-14, 01:47

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

science_man_88 · 2017-10-14, 02:10

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.

ThomRuley · 2017-10-14, 02:23

I'm pretty sure I'm missing something too. That's why I was hoping someone could maybe explain it a different way.

science_man_88 · 2017-10-14, 14:58

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.

Pascal Ochem · 2017-10-14, 20:05

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.

science_man_88 · 2017-10-14, 20:56

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

Pascal Ochem · 2017-10-14, 22:12

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 ?

science_man_88 · 2017-10-14, 22:19

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.

Pascal Ochem · 2017-10-14, 23:42

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.

ThomRuley · 2017-10-15, 19:34

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?

Pascal Ochem · 2017-10-16, 16:56

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)).

2017-10-14, 01:47	#1
ThomRuley May 2003 11110111₂ 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-16, 16:56	#11
Pascal Ochem Apr 2006 61₁₆ 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
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

2017-10-14, 02:23	#3
ThomRuley May 2003 367₈ 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, 20:05	#5
Pascal Ochem 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.

2017-10-14, 22:12	#7
Pascal Ochem Apr 2006 61₁₆ 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, 23:42	#9
Pascal Ochem Apr 2006 97 Posts	You are referring to circumvention of roadblocks. This is a different kind of problem. end game: Suppose that N is coprime to 357111331. Give a lower bound on N. circumvention of roadblock: Suppose N < 10^2100. Suppose that N is coprime to 12719. 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.