mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2012-04-03, 15:28   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110111000102 Posts
Default Generating Low-Weight Ks

Thomas11 how do you generate these rediculously low weight ks? How long does it take to find them?
henryzz is offline   Reply With Quote
Old 2012-04-03, 17:59   #2
Thomas11
 
Thomas11's Avatar
 
Feb 2003

77416 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
File Type: zip multi4d.zip (2.7 KB, 151 views)

Last fiddled with by Thomas11 on 2012-04-03 at 18:16
Thomas11 is offline   Reply With Quote
Old 2012-04-04, 10:30   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

133428 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2012-04-04, 12:01   #4
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22·32·53 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
File Type: zip tools.zip (1.8 KB, 141 views)

Last fiddled with by Thomas11 on 2012-04-04 at 12:09
Thomas11 is offline   Reply With Quote
Old 2012-04-04, 12:29   #5
Thomas11
 
Thomas11's Avatar
 
Feb 2003

77416 Posts
Default

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
File Type: exe Nash100.exe (112.5 KB, 132 views)

Last fiddled with by Thomas11 on 2012-04-04 at 12:41
Thomas11 is offline   Reply With Quote
Old 2012-04-04, 23:50   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

133428 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2012-04-05, 09:16   #7
Thomas11
 
Thomas11's Avatar
 
Feb 2003

22×32×53 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Thomas11 is offline   Reply With Quote
Old 2012-04-05, 15:49   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16E216 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2012-04-06, 12:22   #9
Thomas11
 
Thomas11's Avatar
 
Feb 2003

77416 Posts
Default

Quote:
Originally Posted by henryzz View Post
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 View Post
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
Thomas11 is offline   Reply With Quote
Old 2012-04-09, 21:36   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts
Default

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.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generating from 16 to 35 digit number in row (+1) pepi37 Math 10 2018-03-02 16:50
Generating low weight multipliers Thomas11 Riesel Prime Search 21 2013-08-15 19:34
Generating Random Primes davar55 Math 14 2011-02-20 16:06
Generating 2005 Wacky Puzzles 46 2005-06-05 22:19
Prime-generating polynomials 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.