mersenneforum.org Software/instructions/questions
 Register FAQ Search Today's Posts Mark Forums Read

2009-12-05, 02:48   #45
rogue

"Mark"
Apr 2003
Between here and the

10110110101002 Posts

Quote:
 Originally Posted by Mini-Geek If x*b^1-1, (which is also k-1 when k=xb, which is where we get the k-1 notation) is composite, then k=x and k=xb still remain as possible Riesel numbers. Since from this point on there is no significant difference between the two, we choose to ignore the larger one, k=xb (the same work will be done with k=x). i.e. we remove k's that are multiple of the base when k-1 is composite. If x*b^1-1 is prime, then k=x is eliminated as a Riesel candidate, but k=xb still needs to be checked (although k-1 is of the form xb*b^n-1, it is with n=0 so we don't consider it as a prime that eliminates xb as a Riesel number). i.e. we keep k's that are multiple of the base when k-1 is prime.
The fog has cleared, finally. I think that Gary needs to state this in clear mathematical language in the sticky.

 2009-12-05, 09:11 #46 gd_barnes     May 2007 Kansas; USA 100111101110112 Posts Using the Riesel side as an example, tell me if this is clear enough: 1. n must be >= 1 for all k. 2. If k*b^n-1 where n=1 is prime than k*b (i.e. MOB) will need a different prime because this prime would be kb*b^0-1. 3. If k*b^n-1 where n>1 is prime than k*b will have the same prime (in a slightly different form), i.e. kb*b^(n-1)-1. 4. Assume that k*b^1-1 is prime. k*b^1-1 = kb-1. 5. Conclusion: Per #2 and #4 the only time k*b needs a different prime than k is when kb-1 is prime. (kb+1 for Sierp) If you have a clearer mathematical way of stating it, I'm all ears. The key is orienting it towards people of highly varying mathematical skills. Therefore I just explained what needed to be eliminated and not why for the layman. One more thing: Willem and I independently of one another came to this same conclusion. Although I stated it here first, I think he concluded it before I did. Before we came up with this (likely almost a year into the project), it was a real hassle coming up with which k's that were MOB that needed to be tested. Gary Last fiddled with by gd_barnes on 2009-12-05 at 09:13
2009-12-05, 13:33   #47
rogue

"Mark"
Apr 2003
Between here and the

10110110101002 Posts

Quote:
 Originally Posted by gd_barnes Using the Riesel side as an example, tell me if this is clear enough: 1. n must be >= 1 for all k. 2. If k*b^n-1 where n=1 is prime than k*b (i.e. MOB) will need a different prime because this prime would be kb*b^0-1. 3. If k*b^n-1 where n>1 is prime than k*b will have the same prime (in a slightly different form), i.e. kb*b^(n-1)-1. 4. Assume that k*b^1-1 is prime. k*b^1-1 = kb-1. 5. Conclusion: Per #2 and #4 the only time k*b needs a different prime than k is when kb-1 is prime. (kb+1 for Sierp) If you have a clearer mathematical way of stating it, I'm all ears. The key is orienting it towards people of highly varying mathematical skills. Therefore I just explained what needed to be eliminated and not why for the layman. One more thing: Willem and I independently of one another came to this same conclusion. Although I stated it here first, I think he concluded it before I did. Before we came up with this (likely almost a year into the project), it was a real hassle coming up with which k's that were MOB that needed to be tested.
Let's say k=xb and xb-1 is composite. Let's say that x=yb and yb-1 is composite. If yb^2-1 is prime, we can use it to satisfy the conjecture for x, but not for k. Since x was not tested, we still don't have an n for k.

Does that make sense?

I'm saying that if k = x*b^m and all x*b^j-1 are composite for j<m, then we need to verify that the prime for x is when n>m. I'm not thinking of any examples off the top of my head, but I presume they exist.

2009-12-06, 10:44   #48
gd_barnes

May 2007
Kansas; USA

7·1,453 Posts

Quote:
 Originally Posted by rogue Let's say k=xb and xb-1 is composite. Let's say that x=yb and yb-1 is composite. If yb^2-1 is prime, we can use it to satisfy the conjecture for x, but not for k. Since x was not tested, we still don't have an n for k. Does that make sense? I'm saying that if k = x*b^m and all x*b^j-1 are composite for jm. I'm not thinking of any examples off the top of my head, but I presume they exist.

No, not really. I don't understand what you are getting at.

On the Riesel side is that if k=x and x*b^1-1 (i.e xb-1 or kb-1) is prime, you have to search k=x*b. if x*b^1-1 is composite, then you do NOT have to search k=x*b. It says nothing about any other k values such as k=x*b^2, k=x*b^3, etc.

I suppose you could take it further and say that if x*b^1-1 is composite and x*b^2-1 is prime, you don't have to search k=x*b but you DO have to search k=x*b^2 but that's iterative and confusing IMHO. It's easier to just check to see if k=x*b has a prime at n=1. If so, then k=x*b^2 must be searched. If not, then it doesn't need to be searched. Perhaps that is what you are alluding to?

Put most easily on the Riesel side, if k=x and x-1 is prime, you must search k=x*b. If x-1 is composite, you don't need to search k=x*b. But in neither case can you draw any conclusion about whether you must search k=x*b^2, k=x*b^3, etc.

I would suggest doing some actual tests on this to convince yourself of the fact. After I concluded it mathematically, I had to convince myself with real world examples.

Gary

Last fiddled with by gd_barnes on 2009-12-06 at 10:47

 2009-12-06, 13:58 #49 rogue     "Mark" Apr 2003 Between here and the 22·3·487 Posts I'll have to think this one through. Last fiddled with by rogue on 2009-12-06 at 14:20
 2009-12-06, 14:20 #50 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 17·251 Posts I don't think it really matters. (using k=xb and x=yb) If k-1 is composite, then k is skipped and x will be considered separately, including a MoB check to see if it needs to be run. If k-1 is prime, then x has been eliminated at n=1, and k must be run. This says nothing about y, which will be considered (probably already was, as it's quite a bit smaller than k) as a separate value.
 2010-01-12, 07:52 #51 gd_barnes     May 2007 Kansas; USA 236738 Posts After much thinking and effort, I have now modified the first 3 posts in this thread to reflect more modern udpates as a result of the improvements in PFGW and the new bases script. There has been a lot of confusion on new bases and sieving on this project over its first 2 years. I hope the new bases script along with modification to these postings will clear a lot of that up. Gary
 2010-01-20, 23:51 #52 rogue     "Mark" Apr 2003 Between here and the 22×3×487 Posts I think that it would be useful to have a script (perl, etc.) that could take a pfgw.log file and remove PRPs from pl_remain.txt and candidates from an input file for PFGW in one fell swoop. This would be very useful for bases with higher k to help keep these files in sync as one goes deeper with them. It is very time consuming (with the manual method I am using) to do this. If anyone has an easy way of doing this, I would like to hear about it. I wouldn't be surprised if I have made a mistake with my manual edits. Fortunately I could rebuild pl_remain.txt if I needed to as I have keep the other files from the script and the pfgw.log file.
 2010-01-21, 01:11 #53 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 426710 Posts The Perl script I posted in the first post of http://www.mersenneforum.org/showthread.php?t=12845 can do just that for ABCD (by default, it's easily switchable since it goes through srfile) files, through srfile. It doesn't handle the pl_remain.txt file, but I'd think it'd be fairly easy to make a script based on it that does (or, rather, to modify this script to do it in addition to removing it from the sieve file with srfile). (based on this general idea: for each line in the prime file, get the k and look through pl_remain.txt for it, then remove that line from pl_remain.txt) I'll see about doing that...
2010-01-21, 02:26   #54
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by Mini-Geek The Perl script I posted in the first post of http://www.mersenneforum.org/showthread.php?t=12845 can do just that for ABCD (by default, it's easily switchable since it goes through srfile) files, through srfile. It doesn't handle the pl_remain.txt file, but I'd think it'd be fairly easy to make a script based on it that does (or, rather, to modify this script to do it in addition to removing it from the sieve file with srfile). (based on this general idea: for each line in the prime file, get the k and look through pl_remain.txt for it, then remove that line from pl_remain.txt) I'll see about doing that...
I figured it out, using cygwin tools on Windows (should be practically identical on Linux). Add this after the srfile line:
Code:
    system("grep -v \"@linearray[0]\" pl_remain.txt > temp.txt");
system("sed '1d' temp.txt > pl_remain.txt");
system("del temp.txt");
Here's what they do:
the grep line prints all lines not matching the match string, which is the k, and saves it to temp.txt, but it adds a line saying "File pl_remain.txt:" to the beginning, so...
the sed line removes the first line from temp.txt and prints it to pl_remain.txt
and, of course, the del cleans up by deleting the temp file.

I've tested this briefly. It appears to work.

http://ss64.com/bash/grep.html lists a -h/--no-filename command exists as a "GNU extension", (the cygwin version of grep doesn't support it) so maybe a Linux user could use something like this instead of those other 3 lines:
Code:
    system("grep -hv \"@linearray[0]\" pl_remain.txt > temp.txt");
system("del pl_remain.txt");
system("ren temp.txt pl_remain.txt");
(with del and ren replaced with appropriate Linux equivalents; or maybe there's a more elegant way to write to a file you're reading from...)

I'll post it in the scripts thread too.

Last fiddled with by Mini-Geek on 2010-01-21 at 02:34

 2010-01-21, 04:53 #55 gd_barnes     May 2007 Kansas; USA 7×1,453 Posts I'm confused as to why this is needed. If you use the stop-on-prime option in PFGW or use the new bases script, you should never have any more primes than just the lowest one for each k. There should be no reason to remove any primes. If it is composite PRPs you are referring to, the newest version of the new bases script handles that by writing them to a separate file and continuing to search the k until a "real" prime is found. If it's composite PRPs for higher n-values, i.e. when you wouldn't be using the new bases script, those are so rare that I've never encountered one. I've never seen a composite PRP for an exponent n>1000; on this project anyway. I strongly recommend against manual editing of files for more than one prime on a k; if that is what you are referring to...much too error-prone.

 Similar Threads Thread Thread Starter Forum Replies Last Post __HRB__ Programming 41 2012-07-07 17:43 WraithX GMP-ECM 37 2011-10-28 01:04 gd_barnes No Prime Left Behind 48 2009-07-31 01:44 OmbooHankvald PSearch 3 2005-08-05 20:28 jasong Sierpinski/Riesel Base 5 10 2005-03-14 04:03

All times are UTC. The time now is 02:40.

Wed Aug 5 02:40:21 UTC 2020 up 18 days, 22:27, 1 user, load averages: 1.04, 1.63, 1.69