View Single Post
Old 2013-08-15, 07:50   #11
Thomas11's Avatar
Feb 2003

22×32×53 Posts

Thanks for the further explanation, Citrix!

So, you are splitting the sequence k*2^n-1 into multiple sub-sequences: (k*2^i)*(2^5760)^m-1, where n=5760*m+i. And some of those sub-sequences (or quite many - depending on k) are eliminated by the covering set. This is essentially the idea behind Geoffrey Reynolds' sr1sieve and sr2sieve.

In other words you are just picking some "slices" of n (mod 5760) from the whole sequence. Summing up the weights of all sub-sequences should yield the weight of the original sequence.

If you concentrate on just one (or a few) of those sub-sequences, then it's obviously faster than testing the whole sequence. But typically one has to pick quite a few low weight k's to find at least one prime. Thus, on average it shouldn't make a difference whether to pick a few of the "whole" sequences, or a few hundreds of the ultra-low-weight sub-sequences (out of the same set of k).

To give just a simpler example for illustration:

Let's take k=3, e.g. 3*2^n-1. After some appropriate sieving, there will be even and odd exponents surviving (since k is divisible by 3). We could therefore split the original sequence into even and odd exponents: 3*2^(2m)-1 and 3*2^(2m+1)-1 (= 3*4^m-1 and 6*4^m-1).

Then k=3 in base=4 is just a subset of k=3 in base=2. But if the goal is to test the whole set of k=3 in base=2 up to a given n, then there is no benefit from testing both k=3 and k=6 in base=4 up to m=n/2.

Last fiddled with by Thomas11 on 2013-08-15 at 07:53
Thomas11 is offline   Reply With Quote