mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)

 rogue 2009-12-05 02:48

[QUOTE=Mini-Geek;197836]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.[/QUOTE]

The fog has cleared, finally. I think that Gary needs to state this in clear mathematical language in the sticky.

 gd_barnes 2009-12-05 09:11

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

 rogue 2009-12-05 13:33

[QUOTE=gd_barnes;197887]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.[/QUOTE]

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.

 gd_barnes 2009-12-06 10:44

[quote=rogue;197904]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.[/quote]

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

 rogue 2009-12-06 13:58

I'll have to think this one through.

 Mini-Geek 2009-12-06 14:20

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.

 gd_barnes 2010-01-12 07:52

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

 rogue 2010-01-20 23:51

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.

 Mini-Geek 2010-01-21 01:11

The Perl script I posted in the first post of [URL]http://www.mersenneforum.org/showthread.php?t=12845[/URL] 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)

 Mini-Geek 2010-01-21 02:26

[quote=Mini-Geek;202635]The Perl script I posted in the first post of [URL]http://www.mersenneforum.org/showthread.php?t=12845[/URL] 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 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");
[/code]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.

[URL]http://ss64.com/bash/grep.html[/URL] 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");[/code](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.

 gd_barnes 2010-01-21 04:53

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.

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