mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2006-08-07, 21:01   #34
Harvey563
 
Harvey563's Avatar
 
Apr 2004

11×17 Posts
Default 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: http://www.geocities.com/harvey563/wills.txt

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

Last fiddled with by Harvey563 on 2006-08-07 at 21:19
Harvey563 is offline   Reply With Quote
Old 2006-08-07, 21:04   #35
Citrix
 
Citrix's Avatar
 
Jun 2003

158510 Posts
Default

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

Last fiddled with by Citrix on 2006-08-07 at 21:10
Citrix is offline   Reply With Quote
Old 2006-08-10, 07:25   #36
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by 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 http://www.free-dc.org/forum/showthread.php?t=10262 (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.)
Thanks for this explaination, I am gradually learning about the uses for quadratic residues.

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 http://mathworld.wolfram.com/QuadraticResidue.html) 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 is offline   Reply With Quote
Old 2006-08-11, 23:18   #37
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

I have finished sieving 4*5^n-1 for 0 < n < 200,000 up to p=500e9. (Current status)

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.
geoff is offline   Reply With Quote
Old 2006-08-14, 21:15   #38
antiroach
 
antiroach's Avatar
 
Jun 2003

F416 Posts
Default

Quote:
Originally Posted by geoff View Post
I have finished sieving 4*5^n-1 for 0 < n < 200,000 up to p=500e9. (Current status)

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.
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.
antiroach is offline   Reply With Quote
Old 2006-08-18, 23:16   #39
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by antiroach View Post
At what rate were numbers being removed by the sieve for this range?
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 sieve0-200K.zip
I have started PRP testing to n=90,000, any primes found beyond about n=100,000 should make the top 5000 list.
geoff is offline   Reply With Quote
Old 2006-09-22, 03:47   #40
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default b*(b+1)^n-1

Quote:
Originally Posted by Harvey563 View Post
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 here. 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).
geoff is offline   Reply With Quote
Old 2006-09-22, 16:14   #41
konrad127123
 
konrad127123's Avatar
 
Jun 2005

1000012 Posts
Default

Quote:
Originally Posted by geoff View Post
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)?
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?
konrad127123 is offline   Reply With Quote
Old 2006-09-23, 01:17   #42
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by konrad127123 View Post
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?
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.
geoff is offline   Reply With Quote
Old 2006-09-23, 10:12   #43
konrad127123
 
konrad127123's Avatar
 
Jun 2005

418 Posts
Default

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

Last fiddled with by konrad127123 on 2006-09-23 at 11:04
konrad127123 is offline   Reply With Quote
Old 2006-09-26, 21:47   #44
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
Originally Posted by konrad127123 View Post
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.)
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.
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 136 2021-10-21 16:17
A new sequence devarajkandadai Miscellaneous Math 3 2020-12-01 22:08
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Fun Sequence Sam Kennedy Miscellaneous Math 4 2013-02-07 11:53
What's the next in the sequence? roger Puzzles 16 2006-10-18 19:52

All times are UTC. The time now is 16:23.


Wed Dec 8 16:23:29 UTC 2021 up 138 days, 10:52, 1 user, load averages: 1.27, 1.46, 1.63

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