mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-10-16, 18:18   #12
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
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)).
Using (one) Mertens theorem I see the slightly better: for every eps>0 and for k>k0(eps) it is true that p1<(1+eps)*sqrt(k*log(k)). Some quick computation confirms this (say for k=2e6).
R. Gerbicz is offline   Reply With Quote
Old 2017-10-16, 21:01   #13
ThomRuley
 
ThomRuley's Avatar
 
May 2003

13·19 Posts
Default

Quote:
Originally Posted by Pascal Ochem View Post
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)).
Maybe I'm misunderstanding what it means to "forbid" a factor. I was thinking that meant that the factor would NOT appear at all in an OPN. However, that would not explain why the t2100 file on Pascal's site still has several composites of the form 3^n, 7^n, etc.
ThomRuley is offline   Reply With Quote
Old 2017-10-16, 21:25   #14
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
Maybe I'm misunderstanding what it means to "forbid" a factor. I was thinking that meant that the factor would NOT appear at all in an OPN. However, that would not explain why the t2100 file on Pascal's site still has several composites of the form 3^n, 7^n, etc.
I think the sigma function is the key to your misunderstanding. as the examples given show sigma(sigma(p^n)) is usually a large composite. this would then explain why those numbers are on the site potentially.
science_man_88 is offline   Reply With Quote
Old 2017-10-16, 21:41   #15
ThomRuley
 
ThomRuley's Avatar
 
May 2003

13·19 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I think the sigma function is the key to your misunderstanding. as the examples given show sigma(sigma(p^n)) is usually a large composite. this would then explain why those numbers are on the site potentially.
If a factor has been forbidden, is that only tentative until all the factorizations are done?
ThomRuley is offline   Reply With Quote
Old 2017-10-16, 22:54   #16
Pascal Ochem
 
Pascal Ochem's Avatar
 
Apr 2006

97 Posts
Default

Forget about the word "forbidden". Just consider the proof as a case analysis. We look for an odd perfect N < 10^2000.

First, we consider the case "127 divides N".
So, we explore the tree for 127, which is made of the subtrees for "127^2 || N", "127^4 || N", and so on.
After exploring all the tree for "127 divides N" without finding any N < 10^2000, we consider the other case,
that is, "127 does not divide N".
The assumption "127 does not divide N" is not enough to conclude that N > 10^2000.

So we continue and we consider now the case "19 divides N".
So we suppose both "127 does not divide N" and "19 divides N" and we explore the subtrees for "19^2 || N", "19^4 || N", ...
(Notice that the subtree for "19^2 || N" is quite short).
After exploring all the tree for "19 divides N" without finding any N < 10^2000, we consider the other case,
that is, "19 does not divide N".
The assumptions "127 does not divise N" and "19 does not divide N" are not enough to conclude that N > 10^2000.

So we continue and we consider now the case "7 divides N".
We suppose gcd(N,127*19)=1 and "7 divides N" and we explore the subtrees for "7^2 || N", "7^4 || N", ...
(Notice that the subtree for "7^2 || N" is quite short).
After that , we know that gcd(N,127*19*7)=1, which is still not enough to conclude that N > 10^2000.

We continue in this manner until there only remains the case gcd(N,127*19*7*11*331*31*97*61*13*398581*1093*3*5*307*17)=1.
Now this is sufficient to conclude that N > 10^2000.
Pascal Ochem is offline   Reply With Quote
Old 2017-10-21, 21:07   #17
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

Quote:
Originally Posted by ThomRuley View Post
Maybe I'm misunderstanding what it means to "forbid" a factor. I was thinking that meant that the factor would NOT appear at all in an OPN. However, that would not explain why the t2100 file on Pascal's site still has several composites of the form 3^n, 7^n, etc.
The numbers do not start out forbidden.

The first factor tree is built assuming 127 divides the OPN. It turns out that no OPN less than the threshold is possible if 127 divides the OPN. The next factor tree is built assuming 19 divides the OPN. At this time we know that 127 does not divide our OPN, so any time we reach a branch that would have 127 divide the OPN, we can end that branch. In this sense, 127 is forbidden in the factor tree for 19.

The third factor tree assumes 7 divides the OPN - but we can trim any branch that has 127 or 19 in it because we have already proven that our OPN cannot be divisible by either - hence 127 and 19 are now forbidden in building the third factor tree.

There are factor trees testing for an OPN divisible by 3 and 7. Neither is forbidden until after that factor tree has shown they are impossible. So 3^n and 7^n composites show up in the t1200 file because their factors would simplify the corresponding factor trees (and possibly some of the other factor trees that are created before 3 and 7).
wblipp is offline   Reply With Quote
Old 2017-11-26, 23:23   #18
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

60B16 Posts
Default

Just saw this thread. Pascal, thank you for your kind words about my paper!
Zeta-Flux 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 16:29.

Tue Jan 26 16:29:14 UTC 2021 up 54 days, 12:40, 0 users, load averages: 2.06, 2.05, 2.27

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.