mersenneforum.org Generating Low-Weight Ks
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-03, 15:28 #1 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110111000102 Posts Generating Low-Weight Ks Thomas11 how do you generate these rediculously low weight ks? How long does it take to find them?
2012-04-03, 17:59   #2
Thomas11

Feb 2003

77416 Posts

Quote:
 Originally Posted by henryzz Thomas11 how do you generate these rediculously low weight ks? How long does it take to find them?
I'm using what I call "incomplete covering sets", e.g. "almost" Riesel numbers. Please find the program attached. It's written in plain old Fortran and is related to the one I presented here. Sorry, that it's not very well documented.

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...
Attached Files
 multi4d.zip (2.7 KB, 151 views)

Last fiddled with by Thomas11 on 2012-04-03 at 18:16

 2012-04-04, 10:30 #3 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 133428 Posts I think I vaguly understand how to use the program. You said in post #252 that you had extended the nash weight to 1-100000. 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.
2012-04-04, 12:01   #4
Thomas11

Feb 2003

22·32·53 Posts

Quote:
 Originally Posted by henryzz I think I vaguly understand how to use the program. You said in post #252 that you had extended the nash weight to 1-100000. 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.
Just a little explanation:
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=100000-110000 and n=0-100000). 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
Attached Files
 tools.zip (1.8 KB, 141 views)

Last fiddled with by Thomas11 on 2012-04-04 at 12:09

2012-04-04, 12:29   #5
Thomas11

Feb 2003

77416 Posts

Here comes the Windows binary for the Nash weight (command line) tool.

Usage example:
Code:
Nash100.exe 15
Output:
Code:
                  15 2221 22269
(= k, default Nash weight for n=100000-110000, extended Nash weight for n=0-100000)

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
Attached Files
 Nash100.exe (112.5 KB, 132 views)

Last fiddled with by Thomas11 on 2012-04-04 at 12:41

 2012-04-04, 23:50 #6 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 133428 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 95% of the candidates produced by multi4d turned out to be riesel numbers. Is there any way of finding that within the program?
2012-04-05, 09:16   #7
Thomas11

Feb 2003

22×32×53 Posts

Quote:
 Originally Posted by henryzz 95% of the candidates produced by multi4d turned out to be riesel numbers. Is there any way of finding that within the program?
Note that the sieve length (p<1024) is quite small. Your largest PLIST entry (1153) is above this limit. Thus the program will practically not test for this congruence at all.
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 2012-04-05 at 12:11 Reason: Added another link.

 2012-04-05, 15:49 #8 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 16E216 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.
2012-04-06, 12:22   #9
Thomas11

Feb 2003

77416 Posts

Quote:
 Originally Posted by henryzz 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?
MAXOP is the size of the table of modular orders, e.g. this should be equal (or larger) to the sum of the orders of all primes up to the largest one in your list.
You can obtain the orders in Pari like in the following example:
Code:
znorder(Mod(2,11) = 10
You could easily set MAXOP=100000.
Then remove the "C" (comment) in front of line 137:
Code:
       WRITE (*,*) 'total size of PNTAB :', OPMAX
Then you will see the actual size used, and you may reduce MAXOP to this limit.

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:
 Originally Posted by henryzz 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.
Well, this is the tricky part. A larger covering set does not automatically mean a better one. And as you already noticed: You will quickly reach the limit of 2^63.

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 2012-04-06 at 12:32

 2012-04-09, 21:36 #10 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·29·101 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Math 10 2018-03-02 16:50 Thomas11 Riesel Prime Search 21 2013-08-15 19:34 davar55 Math 14 2011-02-20 16:06 Wacky Puzzles 46 2005-06-05 22:19 Orgasmic Troll Math 28 2004-12-02 16:37

All times are UTC. The time now is 10:35.

Tue Apr 20 10:35:04 UTC 2021 up 12 days, 5:15, 0 users, load averages: 1.87, 1.74, 1.83