mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2009-12-05, 02:48   #45
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

23·52·29 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.
rogue is offline   Reply With Quote
Old 2009-12-05, 09:11   #46
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

23×33×47 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2009-12-05, 13:33   #47
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

23×52×29 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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.
rogue is offline   Reply With Quote
Old 2009-12-06, 10:44   #48
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

23×33×47 Posts
Default

Quote:
Originally Posted by rogue View Post
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.

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
gd_barnes is offline   Reply With Quote
Old 2009-12-06, 13:58   #49
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10110101010002 Posts
Default

I'll have to think this one through.

Last fiddled with by rogue on 2009-12-06 at 14:20
rogue is offline   Reply With Quote
Old 2009-12-06, 14:20   #50
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

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.
Mini-Geek is offline   Reply With Quote
Old 2010-01-12, 07:52   #51
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

23·33·47 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2010-01-20, 23:51   #52
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

16A816 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2010-01-21, 01:11   #53
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts
Default

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...
Mini-Geek is offline   Reply With Quote
Old 2010-01-21, 02:26   #54
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
Mini-Geek is offline   Reply With Quote
Old 2010-01-21, 04:53   #55
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

23·33·47 Posts
Default

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.
gd_barnes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Useless SSE instructions __HRB__ Programming 41 2012-07-07 17:43
Questions about software licenses... WraithX GMP-ECM 37 2011-10-28 01:04
Software/instructions/questions gd_barnes No Prime Left Behind 48 2009-07-31 01:44
Instructions to manual LLR? OmbooHankvald PSearch 3 2005-08-05 20:28
Instructions please? jasong Sierpinski/Riesel Base 5 10 2005-03-14 04:03

All times are UTC. The time now is 06:37.

Fri Jul 10 06:37:24 UTC 2020 up 107 days, 4:10, 0 users, load averages: 1.65, 1.62, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.