20060726, 04:33  #23 
Jun 2003
3×5×107 Posts 
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.
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. 
20060726, 05:35  #24  
Mar 2003
New Zealand
13×89 Posts 
Quote:
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^321. 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?: GFNsieve, AthGFNsieve. Quote:
Last fiddled with by geoff on 20060726 at 05:38 

20060726, 07:37  #25  
Jun 2003
3·5·107 Posts 
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. Last fiddled with by Citrix on 20060726 at 07:38 

20060726, 17:18  #26 
Jun 2003
3·5·107 Posts 
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 http://www.mersenneforum.org/showthread.php?t=4310 (See post by akruppa) Last fiddled with by Citrix on 20060726 at 18:14 
20060728, 03:07  #27  
Mar 2003
New Zealand
13×89 Posts 
Quote:
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. 

20060728, 03:34  #28 
Mar 2003
New Zealand
13×89 Posts 
Factors of 4*5^n1
For the sequence 4*5^n1, 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^n1 end in 1 or 9 when n is odd and k is a square. Can anyone explain this? 
20060728, 04:48  #29  
Jun 2003
3×5×107 Posts 
Quote:
The alogrithm is the same as babystepsgiantsteps algorithm only done in groups of factors of p1, than based on sqrt of the range of n's. so if p1=2*a*b then running time is sqrt(a)+sqrt(2)+sqrt(b) than sqrt(nmaxnmin) Let me know if you have any questions. 

20060729, 23:50  #30  
Mar 2003
New Zealand
1157_{10} Posts 
Quote:
I think the same idea (and the same table) can be used to speed up sieveing for the sequences 2*3^n1, 5*6^n1, 6*7^n1, 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? 

20060802, 01:19  #31  
Jun 2003
1605_{10} Posts 
Quote:


20060803, 03:27  #32  
Mar 2003
New Zealand
13·89 Posts 
Quote:


20060806, 10:08  #33  
Jun 2005
3×11 Posts 
Quote:
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^n1). 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:
If you have time, I recommend reading any good book on "Elementry Number Theory", which will cover such things. Hope this helps :) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Reserved for MF  Sequence 276  kar_bon  Aliquot Sequences  169  20221106 18:03 
A new sequence  devarajkandadai  Miscellaneous Math  3  20201201 22:08 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  sweety439  17  20170613 03:49 
Fun Sequence  Sam Kennedy  Miscellaneous Math  4  20130207 11:53 
What's the next in the sequence?  roger  Puzzles  16  20061018 19:52 