20120403, 15:28  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
Generating LowWeight Ks
Thomas11 how do you generate these rediculously low weight ks? How long does it take to find them?

20120403, 17:59  #2  
Feb 2003
11101110100_{2} Posts 
Quote:
Taking a covering set with modulus=1596424801335 yielding 4 "useful" cycles and testing them up to the 64bit signed integer limit (e.g. 2^63) took about one day on a Q6600 (utilizing all four cores). Computing the Nash weights for the few gigabytes of output and extracting the lowest few hundred Ks from it took another day on that machine. This led to the numbers given here and here. Actually the problem is that this procedure generates quite too many Ks to be tested in finite time. Therefore I stopped after the testing stage and the 4 cycles mentioned above. There might be better (= larger and therefore even lower weighted) covering sets. But this would require some further optimization and a switch to 128 or even 256 bit arithmetic, which I haven't done so far. Perhaps someone else wants to take this project a little further. I would highly appreciate it... Last fiddled with by Thomas11 on 20120403 at 18:16 

20120404, 10:30  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
I think I vaguly understand how to use the program. You said in post #252 that you had extended the nash weight to 1100000. NMAX is only 10000 in the code you provided so I will need to change that to use it. I assume I have read what NMAX is right. CYMIN and CYMAX seem to be parameters controling what cycles you are using. What values have you already searched for the included covering set?
How could I do a quick run producing a few maybe suboptimal ks? Would reducing the size of the covering set speed it up? Currently I am downloading a compiler so I can run it and experiment. 
20120404, 12:01  #4  
Feb 2003
2^{2}·3^{2}·53 Posts 
Quote:
The program (multi4d) is a simple sieve, which I wrote to avoid the much more demanding Nash weight computation. Actually I cannot tell you how fast it is in comparison, but it's MUCH faster. The idea is to do a fast preselection of "good" Ks with multi4d and then compute the Nash weights in a later step for just a small part of those Ks. Therefore NMAX in multi4d is different from the one used in the Nash weight computation. There are two steps in the generation process (multi4d): First generating the congruences using the Chinese Remainder Theorem, and second generating the Ks for a given range of cycles (CYMIN to CYMAX) and sieving them for a given range of n (NMIN to NMAX). The sieve only uses the primes up to p=1021. Therefore it's speed. For you own tests you will need to adjust CYMIN and CYMAX, e.g. start with a small range: CYMIN=0, CYMAX=10000. Depending on your machine this should't take longer than a few minutes (an hour at most). Note that each cycle has a length of 2*MODUL, which is 3192849602670 in the present configuration. With CYMAX=10000 this yields all matching Ks up to 31.9*10^15. Make sure that CYMAX*2*MODUL < 2^63. Note that you will not generate any new numbers by using the present configuration. You will also need to change the part with the PLIST and KMODP (e.g. starting at line 72). This is actually the crucial and tricky part. Here you specify the congruences of the covering set. PLIST contains the primes and KMODP means the required modulus of K with respect to these primes. For your own experiment (and to learn how it works), you may reduce the size of the covering set, let's say to just the primes 3, 5, and 7, by setting NP=9 (line 72). Then the modulus of the covering set is just 3*5*7=105. Then play with the congruences, e.g. setting KMODP to 2, 4, 4, or different values and look at the results. The idea behind is to find the optimal congruences which form the best "incomplete covering sets". The attached ZIP file contains a small Pari script which tries to optimize those congruences. In it's present configuration it uses the set p= {3, 5, 17, 13, 41, 7, 31, 11, 151} with a set length of 120. Note that this differs from the set currently used by multi4d which has a length of 288. The goal is to find congruences which cover all but one position (e.g. 119 out of 120). In other words: Given a range of 120 n values, a sieve for just the primes in the covering set would already eliminate 119 n's. You can run the Pari script multiple times to find all covering sets (it randomly changes the order of the primes of the covering set every time). Note that not all will reach the 1/120 criterion. Also included is the tool for computing the Nash weights (for n=100000110000 and n=0100000). It's only the source code and you will need the GMP library (or MPIR on Windows) to get it compiled. I can also try to make a Windows binary, but this may take a little time. Hope this all makes sense... Kind regards, Thomas Last fiddled with by Thomas11 on 20120404 at 12:09 

20120404, 12:29  #5 
Feb 2003
2^{2}·3^{2}·53 Posts 
Here comes the Windows binary for the Nash weight (command line) tool.
Usage example: Code:
Nash100.exe 15 Code:
15 2221 22269 EDIT: Of course, this is for Riesel Ks. But you can use is for Sierpinski Ks too, just by entering k as k. Therefore it also works for the largest VPS K known so far (found by me and later claimed by Ed Trice): Code:
Nash100.exe 79916753563828279896266938611356192810163128144777193765 79916753563828279896266938611356192810163128144777193765 9613 96121 Last fiddled with by Thomas11 on 20120404 at 12:41 
20120404, 23:50  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
I have it all working now. I didn't find anything useful in my first small test run. I will search more tomorrow. The covering set I am using is 1/288:
Code:
PLIST(1) = 3 PLIST(2) = 5 PLIST(3) = 7 PLIST(4) = 13 PLIST(5) = 17 PLIST(6) = 19 PLIST(7) = 37 PLIST(8) = 97 PLIST(9) = 1153 KMODP(1) = 2 KMODP(2) = 1 KMODP(3) = 1 KMODP(4) = 10 KMODP(5) = 13 KMODP(6) = 9 KMODP(7) = 4 KMODP(8) = 4 KMODP(9) = 941 
20120405, 09:16  #7  
Feb 2003
2^{2}×3^{2}×53 Posts 
Quote:
You could extend the list of primes at the very beginning to some larger limit. But note, that also some other parameters will need to be properly adjusted (MAXP2, MAXOP and perhaps others). But even if your covering set fits the sieve limit there might be a larger Riesel covering set so that you'll get mainly Riesel numbers. It would be a nice side project to find and explore such covering sets. The initial idea of this small sieve (initially only p<512) was that it completely fits into the cache memory of a typical cpu of that time (around the year 2005). Therefore it was quite fast. For modern cpus it could be probably extended to some higher limit while still fitting into the cache. If you're looking for more information about covering sets, Nash weights and the like, you may have a look here and here. Last fiddled with by Thomas11 on 20120405 at 12:11 Reason: Added another link. 

20120405, 15:49  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
I added another 20 primes which leaves it just above 1153 and it made no difference. The files produce were the same. How should I change MAXOP?
The best k I have found so far has an extended nash weight of 18 which is nothing like yours. Is the answer find another covering set or search more? I found some better covering sets but they have slightly more primes and the search range is too small to find anything below 2^63. 
20120406, 12:22  #9  
Feb 2003
1908_{10} Posts 
Quote:
You can obtain the orders in Pari like in the following example: Code:
znorder(Mod(2,11) = 10 Then remove the "C" (comment) in front of line 137: Code:
WRITE (*,*) 'total size of PNTAB :', OPMAX Let me know if you could manage this by yourself. I could send you a modified version earliest on next Tuesday, since I'm currently out of town with only limited internet access. Quote:
These are my typical procedures: (1) Try to find all possible congruences for a given covering set, e.g. by using the Pari script. It will report the lowest k (k0) and the congruences with respect to this k. Depending on your set of primes, there might be multiple (=independend) cycles which all share the same covering set. You may distiguish them by the k0 values. Note that there might be also flip cycles. For the Ks I reported earlier the covering set produced 4 such cycles (at least I found only 4). (2) Find different covering sets. This is mainly trial and error. You could start with known Riesel covering sets and remove one prime or the other. Or replace one prime by a different one (e.g. one with a slightly different modular order). (3) Look at the congruences of known low weight Ks and try to see some pattern. Then try to generate a covering set from this. (4) The systematic procedure: Start with p={3,5} and add primes with increasing orders and matching congruences, while always trying to eliminate all but one of the remaining positions. Last fiddled with by Thomas11 on 20120406 at 12:32 

20120409, 21:36  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
OPMAX is only about 12k so I don't know why I was getting that many riesel numbers. I am away this week. Once I get back I will try to find some useful covering sets.

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 low weight multipliers  Thomas11  Riesel Prime Search  21  20130815 19:34 
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 