Fastest sieving program?
 

I am looking for the fasted sieving program I can use to find (probable) primes of the form k*b^n+-c. Also, which value: k, b, n, or c would be the easiest to (substitute) find primes for? For a sample test, try the form 31*52^n+21, or just fix the variables for this form and choose a high n value.:smile::smile::smile:

I can't find one [URL="http://primes.utm.edu/bios/index.php"]here[/URL]. :sad:

There are plenty of sieves for c=1. This would also make this form provable. :smile:

I looked on a version of Proth's Theorem and says the base b must be prime for k*b^n+1. Is this true?:smile:

srsieve

[QUOTE=PawnProver44;428382]I looked on a version of Proth's Theorem and says the base b must be prime for k*b^n+1. Is this true?:smile:[/QUOTE]

No :no:

[QUOTE=LaurV;428383]srsieve[/QUOTE]

What zip file and script do I need to test the sequence k*b^n+c for fixed k, b, and c (run the file along with Pfgw). Please let me know.:smile:

[QUOTE=LaurV;428383]srsieve[/QUOTE] Thanks. here is [URL="http://primes.utm.edu/bios/page.php?id=905"]the link[/URL]. :smile:

[QUOTE=PawnProver44;428385]What zip file and script do I need to test the sequence k*b^n+c for fixed k, b, and c (run the file along with Pfgw). Please let me know.:smile:[/QUOTE]

[URL="https://sites.google.com/site/geoffreywalterreynolds/programs/srsieve"]srsieve-0.6.17-bin.zip[/URL] and run the ".exe". But first :rtfm:

[QUOTE=paulunderwood;428386]Thanks. here is [URL="http://primes.utm.edu/bios/page.php?id=905"]the link[/URL]. :smile:[/QUOTE]

Do you think any primes of the form k*b^n+-c could make the Top 5000 for primes.utm.edu?:smile:

[QUOTE=PawnProver44;428388]Do you think any primes of the form k*b^n+-c could make the Top 5000 for primes.utm.edu?:smile:[/QUOTE]

No. The current record for Primo is 30k digits. To make the top5000 you need ~400k digits. Only c=+-1 will get you into the top5000, because the proof is rapid.

[QUOTE=paulunderwood;428389]No. The current record for Primo is 30k digits. To make the top5000 you need ~400k digits. Only c=+-1 will get you into the top5000, because the proof is rapid.[/QUOTE]

Any other forms available? The only test that I think would Work is Lucas's Test (N-1), I do not know where I am going to calculate large exponents. Are there any mathematics libraries that would allow me to do large exponent and modular computation?
:smile:

[QUOTE=PawnProver44;428391]Any other forms available? The only test that I think would Work is Lucas's Test (N-1), I do not know where I am going to calculate large exponents. Are there any mathematics libraries that would allow me to do large exponent and modular computation?
:smile:[/QUOTE]

PFGW uses the fastest library on the planet. :boxer:

[QUOTE=PawnProver44;428364]Also, which value: k, b, n, or c would be the easiest to (substitute) find primes for[/QUOTE]

the pairings k and c, and b and c have to be coprime ( aka not share a divisor) for the form to have a chance at being prime. also all primes greater than 3 have to have remainder 1 or 5 when dividing by 6.

[QUOTE=paulunderwood;428392]PFGW uses the fastest library on the planet. :boxer:[/QUOTE]

Are there any other forms I could use to prove large primes besides k*b^n+-1? Just Curious.:smile:

[QUOTE=PawnProver44;428394]Are there any other forms I could use to prove large primes besides k*b^n+-1? Just Curious.:smile:[/QUOTE]

In general: no. As long as you know >12.5% factorisation of N^2-1, you can prove something prime in a reasonable amount of time. For example [URL="http://primes.utm.edu/primes/page.php?id=118734"]this prime.[/URL]

If k (and c) are small the underlying library is faster. :smile:

[QUOTE=paulunderwood;428396]In general: no. As long as you know >12.5% factorisation of N^2-1, you can prove something prime in a reasonable amount of time. For example [URL="http://primes.utm.edu/primes/page.php?id=118734"]this prime.[/URL]

If k (and c) are small the underlying library is faster. :smile:[/QUOTE]

What test would you apply?:smile:

[QUOTE=PawnProver44;428397]What test would you apply?:smile:[/QUOTE]

I am not sure about what you are asking. With 33.333...% of N-1 or N+1 one can use BLS; for 16.666...% of N^2-1 one can use the combined test; with 15% of the factors of N^2-1 one can prove with KP and with >12.5% of N^2-1 one can apply CHG. All can be done in a "reasonable" amount of time.

In prime searching all things are equal... for maximum speed choose k (and c) small, so that the library operates most quickly. Then run a sieve so that the elimination rate is equal to the average PRP test time of the range -- for varying n, this is about 80% of the range. Finally, run PFGW on what the sieve leaves.

[QUOTE=paulunderwood;428398]I am not sure about what you are asking. With 33.333...% of N-1 or N+1 one can use BLS; for 16.666...% of N^2-1 one can use the combined test; with 15% of the factors of N^2-1 one can prove with KP and with >12.5% of N^2-1 one can apply CHG. All can be done in a "reasonable" amount of time.

In prime searching all things are equal... for maximum speed choose k (and c) small, so that the library operates most quickly. Then run a sieve so that the elimination rate is equal to the average of of the range -- for varying n, this is about 80% of the range. Finally, run PFGW on what the sieve leaves.[/QUOTE]

Well in that case, here is an example: say we had large enough n for a probable prime of the form k*149^n +1 (k is large, say 3,000 digits), however we cannot factor k. Is there a way to prove k*149^n+1 prime?:smile:

[QUOTE=PawnProver44;428401]Well in that case, here is an example: say we had large enough n for a probable prime of the form k*149^n +1 (k is large, say 3,000 digits), however we cannot factor k. Is there a way to prove k*149^n+1 prime?:smile:[/QUOTE]

N-1 = k*149^n. So we know some of the factorisation of N-1. Apply what I said above. For k=3,000 digits, any problem numbers can be done with Primo. :smile:

[QUOTE=paulunderwood;428402]N-1 = k*149^n. So we know some of the factorisation of N-1. Apply what I said above. For k=3,000 digits, any problem numbers can be done with Primo. :smile:[/QUOTE]

Do we have to factor k or not in order to prove k*149^n+1 prime? Factoring k would take a long time.:smile:

[QUOTE=PawnProver44;428404]Do we have to factor k or not in order to prove k*149^n+1 prime? Factoring k would take a long time.:smile:[/QUOTE]

:no:

[QUOTE=paulunderwood;428405]:no:[/QUOTE]

Ok, I'll do some of the work to fix the variable n. The k value I am trying to find. That shouldn't be too hard, right :smile::smile::smile:

Fixing n is fine, but keeping k small with give you more speed. Then you are into the territory of PrimeGrid's searches or Riesel Prime Search. :smile:

[QUOTE=PawnProver44;428407]Ok, I'll do some of the work to fix the variable n. The k value I am trying to find. That shouldn't be too hard, right :smile::smile::smile:[/QUOTE]

k*149^n+1 = 6x+1 = (remainder multiplication( k* 5+1) for k*149^n to be usable we can split n into even and odd odd powers of 5 are remainder 5 on division by 6 and, even powers are remainder 1 on division by 6 neither time is b^n going to divide by 6 the factor of 6 must come from k ( aka k must be divisible by 6 for k*149^n+1 to be remainder 1 on division by 6) the other case is k*149^n+1 = 6y+5 = (6y+4) +1 so k*149^n = remainder 4 on division by 6 k*5^n has to have remainder of 4 when divided by 6 we have 5^n splitting into 1 and 5 remainders on division by 6 so k= 6z+4 or 6a+2 respectively ( in respect to order) make sense so so given a particular n you can narrow k down to 2 in every 6 numbers.

[QUOTE=science_man_88;428409]k*149^n+1 = 6x+1 = (remainder multiplication( k* 5+1) for k*149^n to be usable we can split n into even and odd odd powers of 5 are remainder 5 on division by 6 and, even powers are remainder 1 on division by 6 neither time is b^n going to divide by 6 the factor of 6 must come from k ( aka k must be divisible by 6 for k*149^n+1 to be remainder 1 on division by 6) the other case is k*149^n+1 = 6y+5 = (6y+4) +1 so k*149^n = remainder 4 on division by 6 k*5^n has to have remainder of 4 when divided by 6 we have 5^n splitting into 1 and 5 remainders on division by 6 so k= 6z+4 or 6a+2 respectively ( in respect to order) make sense so so given a particular n you can narrow k down to 2 in every 6 numbers.[/QUOTE]

Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?:smile:

[QUOTE=PawnProver44;428410]Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?:smile:[/QUOTE]

If you are going to search fixed n=275523 and b=2, you will not get into the top5000, however you might consider running a [URL="http://www.underbakke.com/primes/"]4-chances sieve[/URL] of a [URL="http://primes.utm.edu/top20/page.php?id=1"]twin prime[/URL] or [URL="http://primes.utm.edu/top20/page.php?id=2"]Sophie Germain[/URL].

[QUOTE=PawnProver44;428410]Thanks for your help. I picked n=275523, so there should be more to eliminate now, right?:smile:[/QUOTE]

so based on what I said k must be 0 or 2 when dividing by 6 for k*149^275523+1 to have potential to be prime. remainder math is also known as modular arithmetic or [TEX]x\equiv g \pmod n [/TEX] where the symbol is a special type of equals and the variables can change. technically using remainder math , you can show that unless [TEX]k(b^n)+c\equiv m \pmod l[/TEX] where m doesn't share a factor with l, that k*b^n+c can't be prime because otherwise the number in question can be represented as a expression using that common factor which it then also shares. example with simpler numbers: [TEX]15\equiv 5 \pmod {10}[/TEX] since 5 and 10 have a common factor 5, one factor of 15 must be 5 so we already know it's not prime.

[QUOTE=paulunderwood;428384]No :no:[/QUOTE]

I think if I remember correct you can always turn a form the doesn't have this restriction into one that does for example 60*152^n+7 can be turned into form k*b^n+7 with b prime with k =60*8^n and b =19 so any factorable number as b can be turned into a prime base by altering k with all the other factors of b raised to the power of n being factored in. I think it's this possibility they may be confusing with necessity. doh [url]http://mathworld.wolfram.com/ProthsTheorem.html[/url] shows that b=2 is proth numbers

If you want to enter the Top-5000 arena, consider checking prime factors of double Mersenne numbers ([url]http://www.doublemersennes.org[/url] ).

[QUOTE=science_man_88;428414]so based on what I said k must be 0 or 2 when dividing by 6 for k*149^275523+1 to have potential to be prime. remainder math is also known as modular arithmetic or [TEX]x\equiv g \pmod n [/TEX] where the symbol is a special type of equals and the variables can change. technically using remainder math , you can show that unless [TEX]k(b^n)+c\equiv m \pmod l[/TEX] where m doesn't share a factor with l, that k*b^n+c can't be prime because otherwise the number in question can be represented as a expression using that common factor which it then also shares. example with simpler numbers: [TEX]15\equiv 5 \pmod {10}[/TEX] since 5 and 10 have a common factor 5, one factor of 15 must be 5 so we already know it's not prime.[/QUOTE]

I noticed that the sequence k*b^n+-c generates infinitely many primes if k + c = b and k and c are coprime.

Example: 96*23^n+73 :smile:

[QUOTE=PawnProver44;428425]I noticed that the sequence k*b^n+-c generates infinitely many primes if k + c = b and k and c are coprime.

Example: 96*23^n+73 :smile:[/QUOTE]

and yet I bet using another mod or a program that takes advantage of factoring algorithms is so far ahead of this that it's not funny I was originally just saying there are conditions on k,b, and c that we can prove allow us to say k*b^n+c can't be prime in certain scenarios.

[QUOTE=science_man_88;428426]and yet I bet using another mod or a program that takes advantage of factoring algorithms is so far ahead of this that it's not funny I was originally just saying there are conditions on k,b, and c that we can prove allow us to say k*b^n+c can't be prime in certain scenarios.[/QUOTE]

We can use modular congruence to fix variables k, b, and c so there are no primes of the form k*b^n+c, for example 3 always divides the sequence 50*13^n+7, and 5: 57*31^n+28:smile:

[QUOTE=paulunderwood;428389]Only c=+-1 will get you into the top5000, because the proof is rapid.[/QUOTE]
There are some exceptions... but they are rare:
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
206 [URL="http://primes.utm.edu/primes/page.php?id=115433"]46821*2^3021380-374567[/URL] 909531 p363 2013
217 18976*2^2976221-18975 895937 p373 2014
1816 [URL="http://primes.utm.edu/primes/page.php?id=104057"]37674760044125*2^1513679-67931[/URL] 455677 p339 2012 (**)
2241 31723*2^1398273-507567 420927 p363 2013 (**)[/CODE]

[QUOTE=Batalov;428457]There are some exceptions... but they are rare:
[CODE]----- -------------------------------- ------- ----- ---- --------------
rank description digits who year comment
----- -------------------------------- ------- ----- ---- --------------
206 [URL="http://primes.utm.edu/primes/page.php?id=115433"]46821*2^3021380-374567[/URL] 909531 p363 2013
217 18976*2^2976221-18975 895937 p373 2014
1816 [URL="http://primes.utm.edu/primes/page.php?id=104057"]37674760044125*2^1513679-67931[/URL] 455677 p339 2012 (**)
2241 31723*2^1398273-507567 420927 p363 2013 (**)[/CODE][/QUOTE]

If you somehow happen to factor k*b^n+-c to 33.33% (rare) you can find primes of the form k*b^n+-c to make the Prime Pages' top 5000.:smile:

What is your mission PawnProver44?
To have few sieve samples, and do LLR and find prime that can go to Top 5000?
I read your topic , and answers from people on this forum.
Use Primegrid data , and start LLR-ing. It is fastest way to find some prime.
You can not compete with the knowledge of mathematics with people on this forum, because everyone knows mathematics far better than you (because of the way your issues)
Another thing is that some of them, if not most, have a much stronger computing power than you had 'em.
And last, it is essential, if not the most important, you need to have luck. I've seen individuals to PrimeGrid which are with very old computers after only a few candidates find prime number, which is entered in the Top 5000 list without problems. But they are rare. All the others have worked or are working for years to achieve something.
Therefore, go and do not ask indefinitely. This is definitely the only way with which you will not find any prime number.

If a mathematician tells you that 2+2=4, then you are wise to take it to the bank.
On the other hand if he tells you that there is no way you can prove that a large [URL="http://primes.utm.edu/glossary/xpage/OrdinaryPrime.html"]ordinary[/URL] prime is prime, ask him to prove it.
If he can't, then it's up to you to take his word as gospel, I wouldn't.:smile:

[QUOTE=a1call;428491]If a mathematician tells you that 2+2=4, then you are wise to take it to the bank.
On the other hand if he tells you that there is no way you can prove that a large [URL="http://primes.utm.edu/glossary/xpage/OrdinaryPrime.html"]ordinary[/URL] prime is prime, ask him to prove it.
If he can't, then it's up to you to take his word as gospel, I wouldn't.:smile:[/QUOTE]

There are several PRPs on [url]http://www.primenumbers.net/prptop/prptop.php[/url] that are of the form k*b^n+c and are about 20,000 to 80,000 digits, if those can't be proven prime, then It would be harder to prove a number 5 times that size prime (of the form k*b^n-+c). It is still possible, but very hard. :smile:

[QUOTE=pepi37;428479]What is your mission PawnProver44?
To have few sieve samples, and do LLR and find prime that can go to Top 5000?
I read your topic , and answers from people on this forum.
Use Primegrid data , and start LLR-ing. It is fastest way to find some prime.
You can not compete with the knowledge of mathematics with people on this forum, because everyone knows mathematics far better than you (because of the way your issues)
Another thing is that some of them, if not most, have a much stronger computing power than you had 'em.
And last, it is essential, if not the most important, you need to have luck. I've seen individuals to PrimeGrid which are with very old computers after only a few candidates find prime number, which is entered in the Top 5000 list without problems. But they are rare. All the others have worked or are working for years to achieve something.
Therefore, go and do not ask indefinitely. This is definitely the only way with which you will not find any prime number.[/QUOTE]

If you looked on my last post, [url]http://mersenneforum.org/showthread.php?t=21065[/url] I wanted to find (probable) primes of the form k*b^n+c (large enough) I was hoping the sieving would be faster. I gave up on finding large (probable) primes of the form 60*79^n+19, sice it takes too long to test exponents, so now I just use random k*b^n+c forms.

[QUOTE=PawnProver44;428492]There are several PRPs on [URL]http://www.primenumbers.net/prptop/prptop.php[/URL] that are of the form k*b^n+c and are about 20,000 to 80,000 digits, if those can't be proven prime, then It would be harder to prove a number 5 times that size prime (of the form k*b^n-+c). It is still possible, but very hard. :smile:[/QUOTE]
So your mission is to find lets say 450.000 digit long PRP and prove it is prime?
Very specific wish :)
Good luck on your hunt for PRP :smile:

[QUOTE=pepi37;428532]So your mission is to find lets say 450.000 digit long PRP and prove it is prime?
Very specific wish :)
Good luck on your hunt for PRP :smile:[/QUOTE]

Do you seriously mean that, or are you just joking around?

My other post was useless.