Williams' sequence 4*5^n-1 (A046865)

[Harvey563]

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

[Citrix]

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

[geoff]

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]

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.

[antiroach]

Originally Posted by geoff

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.

[geoff]

Originally Posted by antiroach

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]

Originally Posted by Harvey563

Results are here: http://www.geocities.com/harvey563/wills.txt

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).

[konrad127123]

Originally Posted by geoff

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?

[geoff]

Originally Posted by konrad127123

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.

[konrad127123]

Originally Posted by geoff

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.)

[geoff]

Originally Posted by konrad127123

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.