20130801, 08:21  #1  
Feb 2003
5·383 Posts 
Generating low weight multipliers
Quote:
I will post them once I'm back. In the meantime you may have a look here. Last fiddled with by Thomas11 on 20130801 at 08:24 

20130802, 07:31  #2  
Jun 2003
5×317 Posts 
Quote:
I tried to write some code to generate these numbers on my own. I extended the k's beyond 64 bits. Using covering sets I have generated some of the lowest weight k's ever know (ultraextremetiny low weight). After sieving less than 1 candidate in 1 million remains. (close to 1.5 in 2 Million) Here is one example. (I can share more if any one needs them) k=6642510166838280632766408995039562371 Covering set=61130828015333178565632041818522446870 n=103680 You can generate more k's by k=k+covering set *y I am currently working on y 110000. I am using PFGW to sieve and factor After sieving for the covering set only n=35346 (mod 103680) remain. Feel free to reserve a range after the first 10000 if you like. I have millions more of such k's if any one is interested. It would be interesting if a prime can be found for such a low weight k. Last fiddled with by Citrix on 20130802 at 07:32 

20130812, 14:24  #3  
Feb 2003
5×383 Posts 
Hi Citrix,
I'm glad to see that you generated a new bunch of ultra low weight Ks. Quote:
Note that there are many more cycles sharing the same covering set. Thus, your starting k (k0) is only one out of many. Here are a few more: 13349413408324173624146033148581 53562291021239919328906722016303 156820614115299139492807442264081 

20130812, 15:12  #4  
Feb 2003
5×383 Posts 
Quote:
k = (2*k + (covering set)/2) (mod covering set) This also means that your k is actually not the smallest k of the cycle. In your case k0=27877812802424205899986999806089. Last fiddled with by Thomas11 on 20130812 at 15:22 

20130812, 20:00  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,939 Posts 
Do you have a method of sieving these?
The only siever I have found that does such large ks is http://fatphil.org/maths/ksieve/ It only works if the k is made up of factors <10^15 though which rules most of these out. 
20130812, 20:25  #6 
Feb 2003
5·383 Posts 

20130812, 22:03  #7 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5,939 Posts 
I suppose once you take into account the covering set there aren't many ns anyway.

20130813, 20:22  #8  
Jun 2003
5·317 Posts 
Quote:
I don't think the size of the k will make any difference as all the k's generated will be low weight. Also k=64 bit would not be faster than these larger k's. Since these numbers take too long to LLR I turned the problem around... and took k numbers less than 2^18. Then I split the k into base 2^5760 sequences. k1=k*2^1 k2=k*2^2 ... and so on. I tested their weight using the above covering set (for 2^57601) & sieving to 1200 Only a few k remained with less than 20 candidates up to 1 million (corresponding to nash weight of 1/4). I have tested some of these to 2 Million with no prime. There are more left if any one is interested. These can be sieved using srsieve. Any thoughts of a group project? Last fiddled with by Citrix on 20130813 at 20:38 

20130814, 17:22  #9  
Feb 2003
5×383 Posts 
Quote:
However, I must admit that I don't understand the explanation of your approach. You say you're taking k<2^18, which is just k<262144  pretty small. But there are no really low weight Ks in the interval, only a few have Nash weights < 100, the lowest weight being 29 for k=138847  about 100 times larger than the 1/4 you mentioned. Then you write: k1=k*2^1 k2=k*2^2 ... which leaves k essentially unchanged. It's just a cycling through the n. k1, k2, ... all have the same weight (in practise: more or less, since the n range is shifted to higher n due to the multiplier 2^i). Then you mention the covering set for 2^57601. Given the divisors of 5760 (= 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 128, 144, 160, 180, 192, 240, 288, 320, 360, 384, 480, 576, 640, 720, 960, 1152, 1440, 1920, 2880, 5760), this means a huge covering set, leading to k much larger than 64 bits or even 128 or 256 bits. Or did you mean a covering set of length 5760 (=2^7 * 3^2 * 5)? This, on the other hand, would be too small. Most likely I missed some essential part of your idea. Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing... 

20130814, 22:12  #10  
Jun 2003
5·317 Posts 
Quote:
2) The more k's you test, the more likely you are to find a small weight k 3) using the covering set of just 3 there are 2 kinds of k> 1/2 the candidates are divisible by 3 or no candidate is divisible by 3 (where k is a multiple of 3). If you tested up to n=10000 then you get weights of 5000, 10000 4) Now using a covering set of 3, instead of using base 2.. you go to base 4, but test only to n=5000. you have 262144*2 k's. (as all k's less than 262144 and these k*2; ie k1=k & k2=k*2) 5) If a k is not a multiple of 3, then for k1 and k2 you will either get 0 or the weight that would be the same for base 2. For numbers that are multiples of 3.. you generated 2 new k weights. for k1 and k2 Repeating the above process for the covering set of 2^57601 {3, 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 97, 163, 193, 271, 541, 641, 769} you can generate k that have low weight but are to be tested for base=2^5760. Then you can sieve up to 1200 to get an approximate nash weight. But given the extremely small weight of these k, you increase the n=1000000 Here are the numbers I generated with number of candidate remaining. The first 40 have been tested to 2M. The others to 250K. I hope this makes sense. 

20130815, 07:50  #11 
Feb 2003
11101111011_{2} Posts 
Thanks for the further explanation, Citrix!
So, you are splitting the sequence k*2^n1 into multiple subsequences: (k*2^i)*(2^5760)^m1, where n=5760*m+i. And some of those subsequences (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 subsequences should yield the weight of the original sequence. If you concentrate on just one (or a few) of those subsequences, 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 ultralowweight subsequences (out of the same set of k). To give just a simpler example for illustration: Let's take k=3, e.g. 3*2^n1. 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^m1 and 6*4^m1). 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 20130815 at 07:53 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generating from 16 to 35 digit number in row (+1)  pepi37  Math  10  20180302 16:50 
Generating LowWeight Ks  henryzz  Riesel Prime Search  9  20120409 21:36 
Generating Random Primes  davar55  Math  14  20110220 16:06 
Generating 2005  Wacky  Puzzles  46  20050605 22:19 
Primegenerating polynomials  Orgasmic Troll  Math  28  20041202 16:37 