mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Open Projects (https://www.mersenneforum.org/forumdisplay.php?f=80)
-   -   Williams' sequence 4*5^n-1 (A046865) (https://www.mersenneforum.org/showthread.php?t=6131)

 Harvey563 2006-08-07 21:01

distribution of Williams primes

I just checked b*(b+1)^n-1 for b from 2 to 512, and n from 1 to 512.

Results are here: [URL="http://www.geocities.com/harvey563/wills.txt"]http://www.geocities.com/harvey563/wills.txt[/URL]

No prime values found for b = 37, 61, 82, 97, 112, 124, 127, 187, 226, 227, 232, 253, 267, 282, 292, 346, 356, 370, 382, 400, 415, 416, 442, 457, 477, 487, 493. I'm going to look at higher n values of these b.
If anyone wants to share their results, post or email me them & I'll update the website.

Harvey563
:whistle:

 Citrix 2006-08-07 21:04

b=127 has been checked by RPS to 575K. So no need to waste time there.

 geoff 2006-08-10 07:25

[QUOTE=konrad127123]If I remember correctly, a similar idea can be used for *all* sequences of the form k*b^n+/-c.Have a look at [url]http://www.free-dc.org/forum/showthread.php?t=10262[/url] (in particular look at post #6). It is written for base 2 Riesel's, but should be fairly easy to adapt to base 5. You would also need to read up on the Legendre symbol. (I can't remember off the top of my head if the Jacobi symbol is relevant here or not.)
[/QUOTE]

I implemented a filter that avoids sieving a sequence r*A^2+/-B^2 with a prime p unless legendre(-/+r,p)=1. The problem is that calculating the value of the Legendre symbol takes more time than is saved by not sieving the sequence, so I need to find a faster algorithm.

However for |r| <= 6 I can use the form of the primes that have r as a quadratic residue from the table (see near the bottom of [url]http://mathworld.wolfram.com/QuadraticResidue.html[/url]) and so don't need to compute Legendre. Does anyone know whether there is an algorithm for extending the table, or was it worked out by special case reasoning for each |r| <= 6?

 geoff 2006-08-11 23:18

I have finished sieving 4*5^n-1 for 0 < n < 200,000 up to p=500e9. (Current [url=http://www.geocities.com/g_w_reynolds/A046865/status.txt]status[/url])

Version 0.4.2 of srsieve will recognise 4*5^n-1 and only try factors p=1,9 (mod 10), so there is no need to use the patched version or to enter the --mod=10,1,9 command line switch. It may also be faster for some of the other sequences like 2*3^n-1, 5*6^n-1, 6*7^n-1 etc. if anyone is working on those.

 antiroach 2006-08-14 21:15

[QUOTE=geoff;84937]I have finished sieving 4*5^n-1 for 0 < n < 200,000 up to p=500e9. (Current [url=http://www.geocities.com/g_w_reynolds/A046865/status.txt]status[/url])

Version 0.4.2 of srsieve will recognise 4*5^n-1 and only try factors p=1,9 (mod 10), so there is no need to use the patched version or to enter the --mod=10,1,9 command line switch. It may also be faster for some of the other sequences like 2*3^n-1, 5*6^n-1, 6*7^n-1 etc. if anyone is working on those.[/QUOTE]

At what rate were numbers being removed by the sieve for this range? Would it be beneficial to continue sieving this range further or just go ahead with PRPs. I have access to both types of machines (p4 and athlons) so I can help with either kind of work if there is any further need. Also could you provide a copy of the resulting sieve file. Thanks.

 geoff 2006-08-18 23:16

[QUOTE=antiroach;85047]At what rate were numbers being removed by the sieve for this range?[/QUOTE]
I have done up to 550e9 now, I was getting about 45 minutes per factor on a P3/600. It is probably worthwhile sieving a bit further. The sieve file is [url=http://www.geocities.com/g_w_reynolds/A046865/sieve0-200K.zip]sieve0-200K.zip[/url]
I have started PRP testing to n=90,000, any primes found beyond about n=100,000 should make the top 5000 list.

 geoff 2006-09-22 03:47

b*(b+1)^n-1

[QUOTE=Harvey563;84720]Results are here: [URL="http://www.geocities.com/harvey563/wills.txt"]http://www.geocities.com/harvey563/wills.txt[/URL]
[/QUOTE]
For anyone else thinking about sieving these, srsieve 0.5.1 should be quite a bit faster than previous versions with b > 4.

For 4*5^n-1 sieving is up to 1e12 and PRP testing up to n=100,000. Sieve file is [url=http://www.geocities.com/g_w_reynolds/A046865/]here[/url]. Now that the sieve is faster it is probably worthwhile sieving to at least 2e12 or further for PRP testing up to n=200,000. (This is quite a heavy sequence).

[QUOTE=geoff;83655]I will start sieving with srsieve. If anyone else is interested in extending this sequence, perhaps we could add it to the Base 5 Sierpinski/Riesel distributed sieve when I catch up (say when sieving reaches p=200e9)?
[/QUOTE]

Now that sr5sieve has support for the quadratic residue stuff, perhaps we could do this and fill in the gaps (i.e. the sieve ranges where the other k's have been sieved, but 4 hasn't) later?

 geoff 2006-09-23 01:17

[QUOTE=konrad127123;87735]Now that sr5sieve has support for the quadratic residue stuff, perhaps we could do this and fill in the gaps (i.e. the sieve ranges where the other k's have been sieved, but 4 hasn't) later?[/QUOTE]
Yes it would be more efficient. If others are interested enough (post now if you are) in PRP testing to higher levels we should do that, but personally I am happy to stop at n=200,000 and then go on to some of the other b*(b+1)^n-1 sequences.

[QUOTE=geoff;87755]Yes it would be more efficient. If others are interested enough (post now if you are) in PRP testing to higher levels we should do that, but personally I am happy to stop at n=200,000 and then go on to some of the other b*(b+1)^n-1 sequences.[/QUOTE]
I think I'd be interested in doing this. By how much does it reduce the performance of the sieve? Is anyone continuing sieving the 200K<n<2M range at the moment? (I can do this until it catches up with the other ks if needed.)

 geoff 2006-09-26 21:47

[QUOTE=konrad127123;87768]I think I'd be interested in doing this. By how much does it reduce the performance of the sieve? Is anyone continuing sieving the 200K<n<2M range at the moment? (I can do this until it catches up with the other ks if needed.)[/QUOTE]
It shouldn't have a noticable effect on the sieve, but there may be a little extra work for the admins. I haven't done any sieving beyond what the files show.

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