mersenneforum.org Williams' sequence 4*5^n-1 (A046865)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-08-07, 21:01 #34 Harvey563     Apr 2004 11·17 Posts 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
 2006-08-07, 21:04 #35 Citrix     Jun 2003 3×232 Posts 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
2006-08-10, 07:25   #36
geoff

Mar 2003
New Zealand

13×89 Posts

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?

 2006-08-11, 23:18 #37 geoff     Mar 2003 New Zealand 13×89 Posts 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.
2006-08-14, 21:15   #38
antiroach

Jun 2003

22·61 Posts

Quote:
 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.

2006-08-18, 23:16   #39
geoff

Mar 2003
New Zealand

48516 Posts

Quote:
 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.

2006-09-22, 03:47   #40
geoff

Mar 2003
New Zealand

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

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

2006-09-22, 16:14   #41
konrad127123

Jun 2005

3310 Posts

Quote:
 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?

2006-09-23, 01:17   #42
geoff

Mar 2003
New Zealand

13×89 Posts

Quote:
 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.

2006-09-23, 10:12   #43
konrad127123

Jun 2005

3×11 Posts

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

Last fiddled with by konrad127123 on 2006-09-23 at 11:04

2006-09-26, 21:47   #44
geoff

Mar 2003
New Zealand

115710 Posts

Quote:
 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
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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post kar_bon Aliquot Sequences 136 2021-10-21 16:17 devarajkandadai Miscellaneous Math 3 2020-12-01 22:08 sweety439 And now for something completely different 17 2017-06-13 03:49 Sam Kennedy Miscellaneous Math 4 2013-02-07 11:53 roger Puzzles 16 2006-10-18 19:52

All times are UTC. The time now is 03:32.

Tue May 24 03:32:54 UTC 2022 up 40 days, 1:34, 0 users, load averages: 0.90, 1.03, 1.13

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔