mersenneforum.org

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)

geoff 2006-07-16 02:22

Williams' sequence 4*5^n-1 (A046865)
 
The sequence [url=http://www.research.att.com/~njas/sequences/A046865]A046865[/url] is mentioned in secion A3 of R. K. Guy's "Unsolved Problems in Number Theory".

The terms of the sequence are the primes of the form 4*5^n-1, a specific case of Williams' sequences of primes of the form (r-1)*r^n-1.

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

The sequences in other bases, [url=http://www.research.att.com/~njas/sequences/A003307]A003307[/url], [url=http://www.research.att.com/~njas/sequences/A079906]A079906[/url], [url=http://www.research.att.com/~njas/sequences/A046866]A046866[/url], etc. could also be extended, but would have to be sieved individually.

Citrix 2006-07-16 16:45

I am interested in helping out. But what is the open problem related to these numbers? what is the weight of these numbers?

Have you tried to search (b-1)*b^n+1? For fixed n and variable b.
Can b-1 ever be a sierpinki or riesel number for base b?

I am more interested in working on the two questions stated above, if there is no open problems related to these numbers.

:goodposting:

geoff 2006-07-17 01:24

Warning: this sequence tickles a bug present in srsieve versions 0.3.0 to 0.3.6, upgrade to 0.3.7 or later.

[QUOTE=Citrix]I am interested in helping out. But what is the open problem related to these numbers? what is the weight of these numbers?[/QUOTE]

I have to confess I haven't researched further than the entry in Guy, the 'unsolved problem' seems to be the same as for the Mersenne primes (which are of the form (r-1)*r^n-1 with r=2), what is their distribution, is the sequence infinite etc.

If n > 0 and n=2m then 4*5^n-1 = (2*5^m-1)(2*5^m+1), so only the odd terms have to be sieved. Also all the factors for the odd terms appear to end in either 1 or 9, so the sieve speed can be doubled by filtering out those ending in 3 or 7.

[QUOTE]
Have you tried to search (b-1)*b^n+1? For fixed n and variable b.
Can b-1 ever be a sierpinki or riesel number for base b?
[/QUOTE]
No. I don't know. When I posted I was mainly thinking that if we leave it too long it will be harder to catch up to the Base 5 distributed sieve, but if the factors have special properties then it may be better to sieve the sequence seperately anyway.

I only sieved 4*5^n-1 with 0 < n <= 2e6 (the distributed sieve range) up to p=6e9, I will stop there, but will continue sieving a smaller range, say 0 < n <= 200,000 since that should be enough to find a few more terms to extend the sequence.

If anyone is interested in sieving 5*4^n-1 I have posted the current sieve in NewPGen format and a modified version of srsieve which only sieves primes that are 1 or 9 mod 10 [url=http://www.geocities.com/g_w_reynolds/A046865]here[/url].

antiroach 2006-07-17 13:58

i can sieve these for a while. what program would be best(fastest) to test these numbers for primality?

Citrix 2006-07-17 14:30

[QUOTE=Citrix]

Have you tried to search (b-1)*b^n+1? For fixed n and variable b.
Can b-1 ever be a sierpinki or riesel number for base b?
[/QUOTE]

I will try working on this, to see if I can find the sierpinki or riesel numbers. I leave 4*5^n-1 for you.

Thankyou.

fetofs 2006-07-17 15:20

[QUOTE=antiroach]i can sieve these for a while. what program would be best(fastest) to test these numbers for primality?[/QUOTE]

Probably normal 5-base procedure, LLR/PRP for probable primality tests, and OpenPFGW for verifications.

antiroach 2006-07-17 15:46

Sequence has been extended
 
Enter expression followed by carriage return:
4*5^15393+-1
Primality testing 4*5^15393+-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N-1 test using base 3
Running N+1 test using discriminant 7, base 1+sqrt(7)
Running N+1 test using discriminant 7, base 3+sqrt(7)
Calling N+1 BLS with factored part 100.00% and helper 0.11% (300.12% proof)
4*5^15393+-1 is prime! (215.8260s+0.0009s)

Is there someone I can report this to?

antiroach 2006-07-17 23:31

Status Update
 
I sieved the 0<=n<=2M file upto 12e9. Here's the srsieve formatted file: [URL="http://s89744942.onlinehome.us/results.zip"]http://s89744942.onlinehome.us/results.zip[/URL]

I also started factoring the numbers. Im upto like n = 30k. I plan on going upto like n=50k and then im going to switch over to working on the 6*7^n-1 sequence.

geoff 2006-07-18 03:10

[QUOTE=antiroach]4*5^15393+-1 is prime! (215.8260s+0.0009s)

Is there someone I can report this to?[/QUOTE]
Nice one :-) There is a [url=http://www.research.att.com/~njas/sequences/Submit.html]submission page[/url], but I think it has to be checked manually by someone, so it is probably best to wait until you have finished working on the sequence and make just one submission for all the new terms you find.

antiroach 2006-07-19 14:08

I prp'd 4*5^n-1 upto n = 50000 without finding any more primes.

geoff 2006-07-20 04:14

I will keep a record of what sieving and PRP testing has been done on the 4*5^n-1 sequence in this [url=http://www.geocities.com/g_w_reynolds/A046865/]directory[/url], but it will probably lag a day or two behind this thread.

konrad127123 2006-07-21 00:49

[QUOTE=Citrix]
Can b-1 ever be a sierpinki or riesel number for base b?
[/QUOTE]
I've proved that if b-1 is a Sierpinski or a Riesel number for base b then it must have an infinite covering set. I can post the proof here if someone wants it.

It might be possible to find a b such that (b-1)*b^n+/-1 factorises nicely for some n (e.g. 4*5^6-1=(2*5^3-1)*(2*5^3+1)) with the rest of the n's having a finite covering set, but I haven't managed yet. I'm still looking into it.

Also, I'm working on the 5*6^n-1 sequence:
5*6^11233-1 & 5*6^13363-1 are both prime with no further primes below 14500

Citrix 2006-07-21 15:53

[QUOTE=konrad127123]I've proved that if b-1 is a Sierpinski or a Riesel number for base b then it must have an infinite covering set. I can post the proof here if someone wants it.
[/QUOTE]

Could you post this or PM it to me?

Thank you.

konrad127123 2006-07-21 20:17

We will treat the Riesel and Sierpinski cases separately (the first part applies to both cases).

Suppose for contradiction, that we have a b, with a finite covering set (for n>0) S={p_1, p_2, ..., p_k}. We can assume wlog (without loss of generality) that all the p_i's are prime. If p_i|b for some i then p_i does not divide (b-1)*b^n+-1. So we can assume wlog that p_i does not divide b for any i. Also, for n>0, (b-1)*b^n+/-1 cannot be even so we can assume that 2 is not in S (this avoids S={2}, which would be a special case for the argument below)

For each n (we have assumed that) there exists a p_i in our set S such that p_i|(b-1)*b^n+/-1.

Riesel case:
consider when n=((p_1-1)*(p_2-1)*...*(p_k-1))-1
If there is an i for which p_i|(b-1)*b^n-1 then
1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)
so b=(b-1)*b^((p_i-1)*c) mod p_i
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so 0=-1 mod p_i. Contradiction! Therefore such a b cannot exist (for Riesels).

Sierpinski Case:
This is quite similar. In this case we let n=((p_1-1)*(p_2-1)*...*(p_k-1))
If there is an i for which p_i|(b-1)*b^n+1 then
-1=(b-1)*b^((p_i-1)*c) mod p_i (for some positive integer c)
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so b=0 mod p_i
So p_i|b. But we assumed that p_i did not divide b. Contradiction!
Therefore such a b cannot exist (for Siepinskis).

Thus we can't have such a b with a finite covering set, so if there exists a b such that (b-1) is Riesel (or Sierpinski) base b, it must have an infinite covering set.

Citrix 2006-07-21 21:15

Your proof is interesting, but flawed.

1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)

C does not exist for all p_i. Hence these p_i can form the covering set.
Your proof if it was correct says that all b-1*b^n-+1 numbers are prime. Which is not true.

konrad127123 2006-07-21 23:32

[QUOTE=Citrix]
1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)

C does not exist for all p_i. Hence these p_i can form the covering set.
Your proof if it was correct says that all b-1*b^n-+1 numbers are prime. Which is not true.[/QUOTE]
c does exist. c=(p_1-1)*(p_2-1)*...*(p_(i-1)-1)*(p_(i+1)-1)*...*(p_k-1) or (equivalently) c=((p_1-1)*(p_2-1)*...*(p_k-1))/(p_i-1)

If there is an i for which p_i|(b-1)*b^n-1 then
(b-1)*b^(((p_1-1)*(p_2-1)*...*(p_k-1))-1)-1=0 mod p_i
so 1=(b-1)*b^(((p_1-1)*(p_2-1)*...*(p_k-1))-1) mod p_i
=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)


My proof definitely does not sat that all such numbers are prime. It says that if you can't cover every value of n for a particular b with a *finite* covering set. It requires an infinite covering set. My proof also doesn't show that (b-1) can never be a Riesel/Sierpinski base b. It does show that if you try to find a b such that b-1 is riesel or sierpinski base b, it just says that you can't find one by looking for just a finite covering set.

(I'm not sure if it was clear or not, but p_j is meant to represent p subscript j)

Citrix 2006-07-22 04:47

Geoff,

A quick question for you. If you consider 4*5^n+1. All n's left after sieving till 3 are multiples of 2 ie. all numbers left are x^2+1. Note that numbers of the form x^(2^y)+1 are generalized fermats and have factors of the form K*2^(Y+1)+1

So for 4*5^n+1 you only have to consider p=4*K+1. This makes sieving twice as fast compared to sieving for all primes.

I am currently working on 625. only numbers of the form 625*2^(4*n) are left. So all factors are of the form p=8K+1. I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.

Thank you in advance for the answer.

geoff 2006-07-24 02:58

[QUOTE=Citrix]I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.[/QUOTE]
Thanks for that suggestion :-) I will have a go at implementing it soon.

geoff 2006-07-25 03:40

[QUOTE=Citrix]I am currently working on 625. only numbers of the form 625*2^(4*n) are left. So all factors are of the form p=8K+1. I was wondering is it possible to make the srsieve only consider these special factors and hence make the sieve faster than newpgen.[/QUOTE]
Even with this idea it seems that NewPGen will still be faster than srsieve for base 2 sequences. At least two base-2 sequences will have to be sieved at once (both with factors of the same form) before srsieve catches up.

Citrix 2006-07-25 05:37

[QUOTE=geoff]Even with this idea it seems that NewPGen will still be faster than srsieve for base 2 sequences. At least two base-2 sequences will have to be sieved at once (both with factors of the same form) before srsieve catches up.[/QUOTE]

NO problem, I plan to do several of them.
[url]http://www.mersenneforum.org/showthread.php?t=6038[/url]

Citrix 2006-07-25 22:59

I am not completely sure, but I think jjsieve already does this for me. k=25 seems faster to sieve than k=5. So I think you do not have to implement anything.

I think when you do discrete log, based on factors of p-1, the first factor 2, eliminates the primes if it does not have the right power of 2 in p-1.


edit:
I am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?

geoff 2006-07-26 03:01

[QUOTE=Citrix]II am working on k=3^16 for base 2^16 from 0 to 2 Million, I am getting about 2150kp/s on a 1.4 ghz p4. What would the speed be for your program, with the above implementation ie. only considering primes 32*a+1?[/QUOTE]
I have implemented your idea in srsieve version 0.3.12, if you use the --verbose switch it will print a message like "Filtering for primes of the form ..." if the special form of the sequence is recognised.

There is one limitation that I may be able to remove in the future: If you sieve two sequences together like (7^2)*2^n+1 and (7^4)*2^n+1, it will sieve both sequences using the same form of factors, i.e. p=x*2^2+1 in this case. If you sieve (7^4)*2^n+1 seperately it can use p=x*2^3+1.

Citrix 2006-07-26 04:33

Thank you for the excellent work. I am getting around 7000 kp/sec for the 3^16 sequence. That is 3.5 times faster than newpgen or jjsieve.:showoff: :bow:

Is there a limit on the size of the k, your program can handle? I would like to test higher values like 3^32 and 3^64 etc.
Does your program have a prover code to submit primes found using your program.

geoff 2006-07-26 05:35

[QUOTE=Citrix]Is there a limit on the size of the k, your program can handle? I would like to test higher values like 3^32 and 3^64 etc.[/QUOTE]
The current limit for k is 2^32-1. It is not a simple matter to increase that without affecting the sieve speed for general sequences.

It would be possible to write a seperate sieve routine that accepts k=a^b where a and b can each be up to 2^32-1. However there are other parts of the program that will limit the speed as b becomes large. In particular the prime sieve generates all primes and then checks to see if each one is of the correct form, this will become very ineffcient when b gets large, and in any case you will soon need to check factors larger than 2^62 which is the modular multiplication limit for the current code.

Have you tried one of these sieves?: [url=http://primes.utm.edu/bios/page.php?id=476]GFNsieve[/url], [url=http://primes.utm.edu/bios/page.php?id=439]AthGFNsieve[/url].

[QUOTE]Does your program have a prover code to submit primes found using your program.[/QUOTE]
The entry is [url=http://primes.utm.edu/bios/page.php?id=905]Srsieve[/url].

Citrix 2006-07-26 07:37

[QUOTE=geoff]The current limit for k is 2^32-1. It is not a simple matter to increase that without affecting the sieve speed for general sequences.

It would be possible to write a seperate sieve routine that accepts k=a^b where a and b can each be up to 2^32-1. However there are other parts of the program that will limit the speed as b becomes large. In particular the prime sieve generates all primes and then checks to see if each one is of the correct form, this will become very ineffcient when b gets large, and in any case you will soon need to check factors larger than 2^62 which is the modular multiplication limit for the current code.

Have you tried one of these sieves?: [url=http://primes.utm.edu/bios/page.php?id=476]GFNsieve[/url], [url=http://primes.utm.edu/bios/page.php?id=439]AthGFNsieve[/url].


The entry is [url=http://primes.utm.edu/bios/page.php?id=905]Srsieve[/url].[/QUOTE]


OK I will stick with this k and not go beyond 2^32

GFNsieve and AthGFNsieve only work with bases<2^32. For me the base is as large as 2^125,000. So I don't think they will work.

Thanks once again for modifying the sieve.

Citrix 2006-07-26 17:18

I noticed that your program does not use the SPH algorithm. Do you have any plans of implementing it. It is quite straight forward. It should make your program several times faster.

It is described here
[url]http://www.mersenneforum.org/showthread.php?t=4310[/url]
(See post by akruppa)

geoff 2006-07-28 03:07

[QUOTE=Citrix]I noticed that your program does not use the SPH algorithm. Do you have any plans of implementing it. It is quite straight forward. It should make your program several times faster.

It is described here
[url]http://www.mersenneforum.org/showthread.php?t=4310[/url]
(See post by akruppa)[/QUOTE]
Thanks for the links, I will have a look at this sometime. I have a feeling the mathematics behind it is more difficult than that behind baby-steps-giant-steps though, it might take me a while.

In srsieve version 0.3.14 I have made the code recognise numbers of the form A^(2^y)+B^(2^y) as generalised Fermats, and there is a bug fix to properly handle cases where the base is a square.

geoff 2006-07-28 03:34

Factors of 4*5^n-1
 
For the sequence 4*5^n-1, can anyone explain why all the factors end in 1 or 9 when n is odd?

I haven't tested many examples, but I think all the odd factors of k*5^n-1 end in 1 or 9 when n is odd and k is a square. Can anyone explain this?

Citrix 2006-07-28 04:48

[QUOTE=geoff]Thanks for the links, I will have a look at this sometime. I have a feeling the mathematics behind it is more difficult than that behind baby-steps-giant-steps though, it might take me a while.

In srsieve version 0.3.14 I have made the code recognise numbers of the form A^(2^y)+B^(2^y) as generalised Fermats, and there is a bug fix to properly handle cases where the base is a square.[/QUOTE]


The alogrithm is the same as baby-steps-giant-steps algorithm only done in groups of factors of p-1, than based on sqrt of the range of n's.

so if p-1=2*a*b


then running time is sqrt(a)+sqrt(2)+sqrt(b) than sqrt(nmax-nmin)

Let me know if you have any questions.

geoff 2006-07-29 23:50

[QUOTE=geoff]For the sequence 4*5^n-1, can anyone explain why all the factors end in 1 or 9 when n is odd?[/QUOTE]

I think I have found part of the answer to this: when n is odd, say n=2m+1, then 4*5^n-1 can be written as 5*x^2-y^2 where x=2*5^m and y=1, and according to a table I found in Guy, the primes with 5 as a quadratic residue are all -1,1 (mod 10).

I think the same idea (and the same table) can be used to speed up sieveing for the sequences 2*3^n-1, 5*6^n-1, 6*7^n-1, but I don't know how to work out the general case yet: Given k, what are the congruence classes of the primes with k as a quadratic residue?

Citrix 2006-08-02 01:19

[QUOTE=geoff]The current limit for k is 2^32-1. It is not a simple matter to increase that without affecting the sieve speed for general sequences.
[/QUOTE]

I think the limit is 2^31-1. I tried sieving k=2249392549 using your program it completely screws the k up, printing incorrect factors etc. If the limit is really 2^32 then I think this is a bug.

geoff 2006-08-03 03:27

[QUOTE=Citrix]I think the limit is 2^31-1. I tried sieving k=2249392549 using your program it completely screws the k up, printing incorrect factors etc. If the limit is really 2^32 then I think this is a bug.[/QUOTE]
Thanks, this is a bug, I'll let you know when it is fixed.

konrad127123 2006-08-06 10:08

[QUOTE=geoff]I think I have found part of the answer to this: when n is odd, say n=2m+1, then 4*5^n-1 can be written as 5*x^2-y^2 where x=2*5^m and y=1, and according to a table I found in Guy, the primes with 5 as a quadratic residue are all -1,1 (mod 10).[/QUOTE]

Correct :). I will try to explain where this table comes from.

Suppose p and q are odd primes. All odd primes are either 1 or 3 (mod 4). The law of Quadratic reciprocity says:

(A)If at least one of p and q is 1 (mod 4) then x^2=p (mod q) has a solution if and only if x^2=q (mod p) has a solution (so either both or neither of these congruences has a solution).

(B)If both p and q are 3 (mod 4) then exactly one of x^2=p (mod q) and x^2=q (mod p) has a solution (this case isn't relevant in the above)

Now let's set q=5. 5=1 (mod 4), so case A applies. Let p be the prime we're trial dividing by. So by case (A) x^2=5 (mod p) will only have a solution if and only if x^2=p (mod 5) has a solution. Substituting in x=0,1,2,3,4 in turn, we find that x^2 (mod 5) must be 0, 1 or 4. So if x^2=5 (mod p) has a solution then x^2 = p (mod 5) has a solution, so p=0,1 or 4 (mod 5).

So x^2=5 (mod p) can only have a solution if p=0,1 or 4 (mod 5). The only prime of the form p=0 (mod 5) is p=5 (which obviously won't divide any number of the form 4*5^n-1). So the only primes left are ones of the form p=1 or 4 (mod 5).

Now let's look at p (mod 10). If p is 1 or 4 (mod 5), then p is 1, 4, 6 or 9 (mod p). If p=4 or 6 (mod 10) then p is even and not equal to 2, so it is not prime. Thus p=1 or 9 (mod 10).

So if x^2 =5 (mod p) has a solution, then p=1 or 4 (mod p), so p=1 or 9 (mod 10), so we only need to consider such primes.

[QUOTE=geoff]I think the same idea (and the same table) can be used to speed up sieveing for the sequences 2*3^n-1, 5*6^n-1, 6*7^n-1, but I don't know how to work out the general case yet: Given k, what are the congruence classes of the primes with k as a quadratic residue?[/QUOTE]

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

If you have time, I recommend reading any good book on "Elementry Number Theory", which will cover such things.

Hope this helps :)

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

konrad127123 2006-09-22 16:14

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

konrad127123 2006-09-23 10:12

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

sweety439 2017-01-21 11:43

I checked (b-1)*b^n+1 for 2<=b<=500, (b+1)*b^n-1 for 2<=b<=300 and (b+1)*b^n+1 for 2<=b<=200.

For the primes of the form (b+-1)*b^n+-1 with integer b>=2 and integer n>=1:

For (b-1)*b^n-1, it is already searched in [URL]http://harvey563.tripod.com/wills.txt[/URL] for b<=2049, but one prime is missing in this website: (91-1)*91^519-1, and the exponent of b=38 is wrong, it should be (38-1)*38^136211-1, not (38-1)*38^136221-1. Besides, (128-1)*128^n-1 has been reserved by Cruelty. The known primes with b<=500 and n>1000 are (38-1)*38^136211-1, (83-1)*83^21495-1, (98-1)*98^4983-1, (113-1)*113^286643-1, (125-1)*125^8739-1, (188-1)*188^13507-1, (228-1)*228^3695-1, (347-1)*347^4461-1, (357-1)*357^1319-1, (401-1)*401^103669-1, (417-1)*417^21002-1, (443-1)*443^1691-1, (458-1)*458^46899-1, (494-1)*494^21579-1. The bases b<=500 without known prime are 128 (n>1700000), 233, 268, 293, 383, 478, 488, all are checked to at least n=200000.

For (b-1)*b^n+1, the known primes with b<=500 and n>500 are (53-1)*53^960+1, (65-1)*65^946+1, (77-1)*77^828+1, (88-1)*88^3022+1, (122-1)*122^6216+1, (158-1)*158^1620+1, (180-1)*180^2484+1, (197-1)*197^520+1, (248-1)*248^604+1, (249-1)*249^1851+1, (257-1)*257^1344+1, (269-1)*269^1436+1, (275-1)*275^980+1, (319-1)*319^564+1, (356-1)*356^528+1, (434-1)*434^882+1. The bases b<=500 without known prime are 123 (n>100000), 202 (reserving, n>1024), 251 (n>73000), 272 (reserving, n>1024), 297 (CRUS prime), 298, 326, 328, 342 (n>100000), 347, 362, 363, 419, 422, 438 (n>100000), 452, 455, 479, 487 (n>100000), 497, 498 (CRUS prime), all are checked to at least n=1024.

For (b+1)*b^n-1, the known primes with b<=300 and n>500 are (63+1)*63^1483-1, (88+1)*88^1704-1, (143+1)*143^921-1. The bases b<=300 without known primes are 208, 232, 282, 292, all are checked to at least n=1024. (except the case b=208, all of them are CRUS primes)

For (b+1)*b^n+1, in this case this b should not = 1 (mod 3), or all numbers of the form (b+1)*b^n+1 are divisible by 3, the known primes with b<=200 (b != 1 mod 3) and n>500 are (171+1)*171^1851+1, there is no such prime with b=201 and n<=1024.

kar_bon 2018-12-07 08:32

4*5^282989-1 is prime! (197802 decimal digits), [url='https://oeis.org/A046865']A046865[/url] changed, continuing.

sweety439 2018-12-14 22:20

[QUOTE=kar_bon;501959]4*5^282989-1 is prime! (197802 decimal digits), [url='https://oeis.org/A046865']A046865[/url] changed, continuing.[/QUOTE]

Where is the wiki... I want the data for all Williams (1st, 2nd, 3rd and 4th) primes (and their dual) for bases b <= 32 ... (and my additional search for b = 38, 83, 88, 93 and 113 ...)

GP2 2018-12-14 23:43

[QUOTE=kar_bon;501959][url='https://oeis.org/A046865']A046865[/url] changed, continuing.[/QUOTE]

I don't see this change in A046865. Maybe it is still stuck in editing?

Is it confirmed that there are no intervening terms between 15393 and 282989? If so, 282989 can be added, but if not, then you should add a comment instead: "282989 is also a member of this sequence".

kar_bon 2018-12-15 10:45

Edits confirmed and I've checked the whole range again, continuing.

Batalov 2018-12-15 17:15

Always press 'these edits are ready for review'. It's a gotcha in the OEIS Wiki.

(It was not always on the Wiki engine, actually.)

kar_bon 2018-12-15 20:30

[QUOTE=Batalov;502892]Always press 'these edits are ready for review'. It's a gotcha in the OEIS Wiki.[/QUOTE]

Yes, overviewd this button on the bottom but got a mail after 7 days without doing so.

kar_bon 2019-01-17 09:21

Found:
4*5^498483-1 is prime! (348426 decimal digits)
4*5^504221-1 is prime! (352436 decimal digits)

Currently at n=695k, OEIS updated.

kar_bon 2019-01-28 09:23

[url='https://primes.utm.edu/primes/page.php?id=125947']4*5^754611-1[/url] is prime: 527452 decimal digits.

kar_bon 2019-02-25 15:32

[url='https://primes.utm.edu/primes/page.php?id=126245']4*5^864751-1[/url] is prime: 604436 decimal digits.

I've not updated the OEIS seq with the last two primes, will do after reaching n=1M.

kar_bon 2019-04-04 10:01

4*5^n-1 completed to n=1M and releasing
- no more primes found
- OEIS / Wiki updated
- S.Harvey informed

Dylan14 2019-05-11 23:30

Taking 4*5^n-1 beyond n = 1M. Will probably take it to 1.5 M, or until I am bored.


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.