20171128, 07:44  #1 
"Sam"
Nov 2016
5×67 Posts 
Sieve for divisibility sequences
Prior to other existing sieving programs, it would be convenient to have a sieve for divisiblity sequences S(n) (prime n only) which include, but are not restricted to (a^nb^n)/(ab), LucasU(a,b,n), and LucasV(a,b,n).
The idea is that there are three arguments to the sieve, S(n) the sequence (already defined), the primes n in the range [a, b], and the sieve limit l, to which S(n) is trial divided by primes of the form 2*k*n+1 (or in some sequences trial divide by primes of the form 2*k*n+1) with k <= l. The sieve formats should be similar to that of other programs, such as in perl ntheory, msieve, srsieve, etc: [S(n),a,b,l,1] to sieve S(n) for prime indices n, in the range [a,b] and divide by prime numbers of the form 2*k*n+1 up to k = l. [S(n),a,b,l,1] to sieve S(n) for prime indices n, in the range [a,b] and divide by prime numbers of the form 2*k*n+1 or k*n1 up to k = l. For instance, if one chooses to test S(n) = 2^n1 for odd prime n up to 100, with l = 10000, the input is: [2^n1,3,100,10000,1] and output are the primes: [19, 31, 61, 67, 89] because these primes are not divisible by any prime factor of the form 2*k*n+1 with k < 10000. One can write an ABC file (if there are several primes remaining in output) or test them manually if there are not many and or they are small values: PFGW Version 3.8.3.64BIT.20161203.Win_Dev [GWNUM 28.6] Primality testing 2^191 [N1, BrillhartLehmerSelfridge] 2^191 is prime! (0.0667s+0.1339s) Primality testing 2^311 [N1, BrillhartLehmerSelfridge] 2^311 is prime! (0.1568s+0.1394s) Primality testing 2^611 [N1, BrillhartLehmerSelfridge] Running N1 test using base 3 2^611 is prime! (0.2173s+0.1997s) Primality testing 2^671 [N1, BrillhartLehmerSelfridge] Running N1 test using base 3 Primality testing 2^891 [N1, BrillhartLehmerSelfridge] Running N1 test using base 3 2^891 is prime! (0.3988s+0.1553s) and find that 2^n1 is prime for n = 2, 3, 5, 7, 11, 13, 17, 19, 31, 61, 89. The first 6 terms are a trivial result of dividing 2^n1 by all prime factors of the form 2*k*n+1, with k > l, and 2*l*n+1 > 2^n1. The others are a result of a primality test after 'sieving'. Other large sequences should work the same way, leaving less primes indices n to test in S(n). 
20220208, 05:20  #2  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7^{2}×73 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A great universal divisibility rule  JM Montolio A  Miscellaneous Math  3  20180227 16:11 
Divisibility sequences based on recurrence relations  carpetpool  Combinatorics & Combinatorial Number Theory  1  20171221 00:42 
Sequences >1M and < 5M  ugly2dog  Aliquot Sequences  21  20150910 07:09 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
Any interest in all sequences/open sequences?  Greebley  Aliquot Sequences  6  20120407 10:06 