News from sub-project Deep Sieving

[LaurV]

Following Serge's idea, if someone likes the pfgw/pari combination to look for primes of this type, and later on, to check if they divide MMp, I can write a small "starting up tutorial" for windoze.

1. First, you have to install pari. Then download pfgw and copy the suitable .exe file into the folder where you run pari (default, this is the folder where you have the gp.exe, and all your .gp scripts). When I say "suitable" I mean "pfgw64.exe" if you run a 64 bit version of windows, or "pfgw32.exe" if you run win32, or whatever.

2. Then, we would need to know what numbers we are testing, if these are double mersenne, then we would need to know first what the mersennes are, therefore I always have "handy" a file called "mprimes.gph" which contains all the exponents of the mersenne primes:

/*this to avoid remembering the primes :D 
in spite of the fact that a mersenne hunter should know all of them by heart :P:P*/
MAX_KNOWN_MERSENNES = 48;
MERSENNE_EXPONENTS = 
{[      2,        3,        5,        7,       13,       17,       19,       31,
       61,       89,      107,      127,      521,      607,     1279,     2203,
     2281,     3217,     4253,     4423,     9689,     9941,    11213,    19937,
    21701,    23209,    44497,    86243,   110503,   132049,   216091,   756839,
   859433,  1257787,  1398269,  2976221,  3021377,  6972593, 13466917, 20996011,
 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161,
 0];
}

You can copy this code in a file called "mprimes.gph" (the "h" is intended same as the "h" files of C projects, a header file). The advantage of having them separate is that you can load them in pari every time with a simple command like "\r mprimes.gph" and do whatever you like with them. You can also include them in the "conf" file and have them available every time pari/gp starts. They are very "handy", you don't need to remember the exponents allways... (well.. see the comment in the code)..

3. Next, we need to create the "working environment" for testing. I will assume below that you have win64 and use pfgw64.exe to check the numbers for primality.

We will create a small pari script, called "mmpp_create.gp", with the content below:

\r mprimes.gph
{for(i=13,MAX_KNOWN_MERSENNES, 
    system("md MM"i);
    system("copy /b pfgw64.exe MM"i"\\pfgw64.exe");
    write("MM"i"\\m"i,"2^"MERSENNE_EXPONENTS[i]"-1");
    write("MM"i"\\start_"i".bat","pfgw64 -f -e100000 -lmm_"i".log -hm"i" work_"i".txt\npause");
    write("MM"i"\\work_"i".txt","ABC2 8*$a*(2^"MERSENNE_EXPONENTS[i]"-1)+1 | (8*$a+2)*(2^"MERSENNE_EXPONENTS[i]"-1)+1\na: from 1 to 10000000")
);}

4. Now, after you have all the files "mprimes.gph", "mmpp_create.gp", "pfgw64.exe" in the pari/gp folder, you start pari/gp and type the command: "\r mmpp_create"

What you will see, it will be an explosion of 36 folders, from MM13 to MM48, and in each folder you will have 4 files, "ready to run".

Caution! do not load/run the "create" file second time, before "cleaning" (i.e. deleting the MMxx foders), otherwise he will "add" lines to the files already created, messing the things ugly. The script can be improved to do the cleaning first, but this is beyond the current "small" tutorial. After you "\r mmpp_create" once, then you will *NEVER* need this file again , this file is only to create all the folder structure to help you hunting, so you don't need to copy and edit 36 folders and 100 files by yourself.

5. Go to one of the foders, say "MM21" (chose an averaged one, to have an idea about the speed!, but not only, see below more reasons to start with an "average", until you understand how this works) and directly run the .bat file (check its contents first, if you like).

6. Enjoy! (like someone would say, "Profit!" )

-----------

Remark: in each folder you run the start.bat file, it will call pfgw to hunt for primes of the desired form. You can run more instances, from different folders, when you have more cores available. You will need to edit the ABC2 files (that is the "work_xx.txt" files) to hunt in different ranges. If we wanna do this as a group project, someone should coordinate the ranges, to avoid duplications. (NOT ME!)

When running, pfgw will create two log files, one with all the work it does (called "mm_XX.log", where XX is your MM number), and one with prime numbers (called "pfgw.log", this name can not be changed by option switches). For "smaller" MMP, like from 13 to 25, the log file grows very fast, so it makes sense to modify the "work_XX.txt" files (this is the "work to do") to use lower limits in the second line. You may need to modify the work file anyhow if you delete the big log file for space reasons. Pfgw is enough clever to resume properly if you keep the log, but if it is really big, and you need to delete it, then you must edit the work file and increase the "from" limit, to avoid duplication of work.

Do not delete the "prime logs". You may want to report them, or use pari to check if they divide MMp or not. About this, in a further post. Generating primes for MM13-MM25 or so, is a very fast process. You get a prime every few seconds, in average.

Also, it may make sense to use the "-t" switch, to have them "proved" primes, before going to test them, especially for larger one (where the test takes some time), and that is why we created the "mXX" files, the one without extension, they are used in primality proving, see Serge's post above.

To use the "-t", you can edit the ".bat" files manually, or you can put add it in the "mmpp_create.gp". If you use the "-t", the "prime log" file will be called "pfgw_primes.log" (again, it can not be changed from the option switches) and it will contain proved primes. You can report them, or check if they are factors of MMxx.

Important: be careful, this tutorial will only test numbers of the form 2*k*Mp+1, where Mp is a mersenne prime, and k is either 0 or 1 (mod 4). It will *NOT* test numbers for which k is 2 or 3 (mod 4) as those numbers, in spite of the fact they can be prime, they cannot divide MMp.

Also, due to the observation above, the "search" was optimized a bit, see the expressions in the ABC2 form: because k=4x or k=4x+1, we substituted it in the factor form, so we use 8*x*Mp+1 and (8*x+2)*Mp+1. This means that if you search for primes with x from 0 to 20000, you in fact covered a "k range" (in 2kMp+1) for times larger, from 0 to 80000.

More clearly, when your screen shows that you are testing 8*54321*(2^9689-1)+1, you in fact are testing k=4*54321 which is k=217284. Also, if your screen shows that you are testing (8*654321+2)*(2^9689-1)+1, you in fact are testing k=4*654321+1 which is k=2617285.

(the things happens 4 times faster than you see on screen)


Edit: example of found primes, for the discussed case above: ("-t" was not used, but a recheck with "-t" enabled indicated first 6 of them being prime, then I interrupted it after about 5 minutes. In fact at this size, they all should be prime, i.e. the chance to get a pseudoprime of this form and this size is zero, it is few orders of magnitude smaller than to get a prime). These numbers are for demo only, we know from the past that none of them divide MM#21.

(8*218+2)*(2^9689-1)+1
(8*3398+2)*(2^9689-1)+1
(8*3895+2)*(2^9689-1)+1
8*4470*(2^9689-1)+1 
8*4845*(2^9689-1)+1 
(8*6443+2)*(2^9689-1)+1
(8*8072+2)*(2^9689-1)+1
8*11957*(2^9689-1)+1 
8*17571*(2^9689-1)+1 
8*17819*(2^9689-1)+1 
8*18122*(2^9689-1)+1 
8*18851*(2^9689-1)+1 
(8*20395+2)*(2^9689-1)+1
(8*20432+2)*(2^9689-1)+1
(8*21811+2)*(2^9689-1)+1
(8*22175+2)*(2^9689-1)+1
(8*24817+2)*(2^9689-1)+1
8*25826*(2^9689-1)+1 
(8*26170+2)*(2^9689-1)+1
(8*26965+2)*(2^9689-1)+1
(8*29621+2)*(2^9689-1)+1
(8*30362+2)*(2^9689-1)+1
8*30644*(2^9689-1)+1 
(8*32146+2)*(2^9689-1)+1
8*33737*(2^9689-1)+1 
(8*34217+2)*(2^9689-1)+1
8*35442*(2^9689-1)+1 
8*36846*(2^9689-1)+1 
(8*40385+2)*(2^9689-1)+1
8*40781*(2^9689-1)+1 
(8*42983+2)*(2^9689-1)+1
8*44309*(2^9689-1)+1 
8*44385*(2^9689-1)+1 
8*45584*(2^9689-1)+1 
(8*46678+2)*(2^9689-1)+1
(8*46727+2)*(2^9689-1)+1
(8*47077+2)*(2^9689-1)+1
8*47184*(2^9689-1)+1 
8*47684*(2^9689-1)+1 
8*53322*(2^9689-1)+1 
(8*55163+2)*(2^9689-1)+1
(8*56492+2)*(2^9689-1)+1
8*56649*(2^9689-1)+1 
(8*57121+2)*(2^9689-1)+1
(8*57185+2)*(2^9689-1)+1
8*62102*(2^9689-1)+1 
8*63131*(2^9689-1)+1 
(8*64688+2)*(2^9689-1)+1
(8*66566+2)*(2^9689-1)+1
(8*66776+2)*(2^9689-1)+1
(8*67625+2)*(2^9689-1)+1
(8*68507+2)*(2^9689-1)+1
(8*68830+2)*(2^9689-1)+1
(8*70633+2)*(2^9689-1)+1
8*72497*(2^9689-1)+1 
(8*76562+2)*(2^9689-1)+1
(8*77591+2)*(2^9689-1)+1
8*79964*(2^9689-1)+1 
8*80102*(2^9689-1)+1 
(8*80750+2)*(2^9689-1)+1
(8*82046+2)*(2^9689-1)+1
(8*83302+2)*(2^9689-1)+1
8*84045*(2^9689-1)+1 
(8*84857+2)*(2^9689-1)+1
(8*86728+2)*(2^9689-1)+1
(8*87418+2)*(2^9689-1)+1
8*87699*(2^9689-1)+1 
(8*88523+2)*(2^9689-1)+1
(8*90386+2)*(2^9689-1)+1
(8*92501+2)*(2^9689-1)+1
8*93561*(2^9689-1)+1 
(8*95042+2)*(2^9689-1)+1
8*95697*(2^9689-1)+1 
8*102057*(2^9689-1)+1 
(8*103837+2)*(2^9689-1)+1
8*105872*(2^9689-1)+1 
(8*106930+2)*(2^9689-1)+1
8*107709*(2^9689-1)+1 
(8*110833+2)*(2^9689-1)+1
8*111020*(2^9689-1)+1 
(8*111283+2)*(2^9689-1)+1
8*111314*(2^9689-1)+1 
8*112781*(2^9689-1)+1 
8*115476*(2^9689-1)+1

[aketilander]

Resuming input file input.txt at line 2
                                    
Resuming at bit 2266723                                    
2*185*(2^43112609-1)+1 is composite: RES64: [CB3659FA0EA37681] (2183200.7866s+0.0091s)

Resuming input file input.txt at line 2
                                    
Resuming at bit 2898761                                    
Resuming input file input.txt at line 2
                                    
Resuming at bit 46825600                                    
Resuming input file input.txt at line 2
                                    
Resuming at bit 56092800                                    
2*45*(2^57885161-1)+1 is composite: RES64: [93AEF93107834320] (113763.1030s+0.0113s)

[ET_]

Originally Posted by aketilander

Resuming input file input.txt at line 2
                                    
Resuming at bit 2266723                                    
2*185*(2^43112609-1)+1 is composite: RES64: [CB3659FA0EA37681] (2183200.7866s+0.0091s)

Resuming input file input.txt at line 2
                                    
Resuming at bit 2898761                                    
Resuming input file input.txt at line 2
                                    
Resuming at bit 46825600                                    
Resuming input file input.txt at line 2
                                    
Resuming at bit 56092800                                    
2*45*(2^57885161-1)+1 is composite: RES64: [93AEF93107834320] (113763.1030s+0.0113s)

So you did both of them!

Nice job, thanks!

Luigi

[ET_]

Another small update:

M( M( 23209 ) )U: k=10000000            # Luigi Morelli, 2013 Nov 17, PARI and pfgw. Stopped.

Luigi

[ET_]

...and a reservation:

M( M( 859433 ) )U: k=100000             # Luigi Morelli, PARI and pfgw. Reserved

Luigi

[ET_]

I completed the pre-sieve phase on MM36 and MM37, all the remaining Ks up to k=2M are tested up to 2T.

Now it's time to attack the remaining Ks with pfgw,: each candidate just requires 4-5 hours to be tested. As you can see from the reservation page at http://www.doublemersennes.org/sieving/reserved.php , I reserved a bunch of them.

If you like, you can help with this work: you may find out a prime factor of 100,000 digits and possibly a divisor of a double Mersenne number.

Meanwhile, I am going on pre-sieving all ks < 2M, taking the limits higher and higher: the picture is the following:

1 - To reach 4T for MM42, MM43 and MM44, 6T for MM45 and MM46, 9T for MM47 ad 13T for MM48.
2 - To add a new upper limit of 45T for the first candidate of MM45->MM48.
3 - To test a GPU-based program for pre-sieving I'm (slowly) working on.

The items #1 and #2 can be easily distributed, just let me know if you are interested. The more you help, thhe more I can develop the new software.

Luigi

[ET_]

Originally Posted by ET_

...and a reservation:

M( M( 859433 ) )U: k=100000             # Luigi Morelli, PARI and pfgw. Reserved

Luigi

Started the pfgw attack for k < 100,000. It will take me less than one month.

For whoever is interested to take on from k=100,000 the list of k that survived sieve up to 205G is attached.

205G has been chosen because at that level the rate of elimination of Ks in the range 10,000-100,000 was lower than the rate of completion of pfgw (about 18 minutes on my old i5-750). If you prefer sieving deeper, I can provide my sieving tools.

Have fun!

Luigi

[ET_]

As the previous thread had a somewhat misleading name, I stick here the thread reserved to discussions about the Deep sieving subproject.

HTH

Luigi

[ET_]

M( M( 756839 ) )U: k=100000             # Luigi Morelli, PARI and pfgw. Reserved

Luigi

[ET_]

M( M( 110503 ) )U: k=2,000,000            # Luigi Morelli, Pari and pfgw, stopped 2014 Feb 12

The k have been tested up to 2,000,000.

17 new primes found, none divides MM29.

The list of primes is attaached.

Luigi

[ET_]

M( M( 132049 ) )U: k=2,000,000            # Luigi Morelli, Pari and pfgw, stopped 2014 Feb 12

The k have been tested up to 2,000,000.

23 new primes found, none divides MM30.

The list of primes is attaached.

Luigi