mersenneforum.org (https://www.mersenneforum.org/index.php)
-   XYYXF Project (https://www.mersenneforum.org/forumdisplay.php?f=110)
-   -   Leyland Primes (x^y+y^x primes) (https://www.mersenneforum.org/showthread.php?t=19347)

 pxp 2020-06-27 14:03

[QUOTE=rogue;549154]Send me one of your lists and I'll sieve with xyyxsieve.[/QUOTE]

Did you mean (for example) my original 17632 Leyland number pairs list that I reduced to [URL="http://chesswanks.com/num/LLPHbdl/386434.txt"]1324 candidate terms[/URL]? Why not just sieve the 1324 terms?

Also, since I am not at all acquainted with xyyxsieve, is the output format of my list appropriate? I have one round-bracketed (x,y) pair per line with a final empty line to indicate end-of-file. I can lose the brackets or make other changes that might make feeding xyyxsieve easier.

 rogue 2020-06-27 15:45

I can work with that file. I just need to manipulate with NotePad++ to be compatible with xyyxsieve.

Here is a sample run of xyyxsieve:

[code]
xyyxsieve -y100 -Y2000 -x1000 -X1900 -s+ -P1e6
xyyxsieve v1.5, a program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
856401 because the term is even
162236 because x and y have a common divisor
Sieve started: 3 < p < 1e6 with 694164 terms (1000 <= x <= 1900, 100 <= y <= 2000) (expecting 638964 factors)
p=432389, 604.0 p/sec, 654967 factors found at 10.75K f/sec, 43.2% done. ETC 2020-06-27 10:40
Sieve completed at p=1000193.
Processor time: 93.38 sec. (0.00 sieving) (1.00 cores)
36802 terms written to xyyx.pfgw
Primes tested: 78512. Factors found: 657362. Remaining terms: 36802. Time: 93.27 seconds.
[/code]

The first few lines of xyyx.pfgw look like this:

[code]
ABC \$a^\$b\$c*\$b^\$a // Sieved to 1000193
1000 319 +1
1000 341 +1
[/code]

which sorted by ascending x then ascending y.

The input has a restriction that maxy must be greater than maxy. I really don't recall why.

If you have the command line tools with Xcode, you can build xyyxsieve fairly easily as a makefile is included.

 pxp 2020-06-28 02:31

[QUOTE=rogue;549154]pfgw will likely be faster ...[/QUOTE]

If I can get it to run. After spending a considerable amount of time trying to unzip the Mac-version download (it defaulted to some really old unarchivers I had squirreled away that couldn't do it), I finally downloaded a more recent app that did the job. Generally on modern Macs one can unzip a .zip file just by double-clicking on it.

Following the Beginner's Manual, I created the shown "input.txt" file and placed it in the "distribution" folder that contained "pfgw64". Double-clicking on pfgw64 opened Terminal and ran through the license and usage text (press enter or ^C). I think I learned that ^C actually means Ctrl-C. The final 'enter' (or ^C any time) always ended with a logout, after which I couldn't type my "pfgw input.txt" or anything else for that matter.

 rogue 2020-06-28 13:23

[QUOTE=pxp;549259]If I can get it to run. After spending a considerable amount of time trying to unzip the Mac-version download (it defaulted to some really old unarchivers I had squirreled away that couldn't do it), I finally downloaded a more recent app that did the job. Generally on modern Macs one can unzip a .zip file just by double-clicking on it.

Following the Beginner's Manual, I created the shown "input.txt" file and placed it in the "distribution" folder that contained "pfgw64". Double-clicking on pfgw64 opened Terminal and ran through the license and usage text (press enter or ^C). I think I learned that ^C actually means Ctrl-C. The final 'enter' (or ^C any time) always ended with a logout, after which I couldn't type my "pfgw input.txt" or anything else for that matter.[/QUOTE]

For the .7z extension, I use Keka to compress/de-compress.

What you need to do is open the Terminal app (Applications/Utilities). Move pfgw64 to a folder that you can access easily from the command line. It is probably under /Users/<your user id>/Downloads or /Users/<your user id>/Downloads/distribution. From there you can execute pfgw64 by typing "./pfgw64" (without the double-quotes) and hitting the enter key. I suggest typing "./pfgw64 -q100^101+101^100" just to verify that it runs a PRP test on that term. Once you get that far, then you just have to replace "-q100^101+101^100" with the name of a file in a pfgw compatible format. The format I showed above is compatible with pfgw.

Once you get a little familiar with the Terminal app (think Unix or Linux), it opens up a world of possibilities for other command line applications such as the mtsieve suite and llr.

If you have other questions, please ask. If I cannot help, there are other Mac users on this forum who can.

 rogue 2020-06-28 13:51

In trying to run xyyxsieve against your file it has issues because there each x has only one y term. With such a large range of x and y, it cannot hold everything in memory.

It would require a custom sieve to avoid excessive memory usage if one wants to do the whole range at once.

I don't know if these candidates have been sieved or not or how deeply Mathematica will trial factor them to. I took a small chunk and sieved to 1e8 and reduced from 307 terms to 97 terms in about 4 minutes. It can clearly sieve more deeply. Sieving to 1e10 should reduce that to about 78 terms.

If you see value in using xyyxsieve, let me know and I'll see what I can do to "whip up" a special version for your search. A "special version" would be memory friendly and twice as fast, if not faster.

 pxp 2020-06-28 23:48

[QUOTE=rogue;549282]From there you can execute pfgw64 by typing "./pfgw64" ...[/QUOTE]

Thank you so much for explaining this. I had actually used ./ on other programs before but I use Terminal so infrequently that I forgot. So I ran this on my 2013 Mac Pro which was already running PrimeQs on six separate Mathematica programs:

[CODE]85085^34812+34812^85085 is composite: RES64: [13D0B9CBFDEA3D81] (3520.8900s+0.0050s)[/CODE]

Under an hour, compared to the 6 hours it had previously taken in Mathematica. I'm blown away!

 pxp 2020-06-28 23:52

[QUOTE=rogue;549286]If you see value in using xyyxsieve, let me know and I'll see what I can do to "whip up" a special version for your search. A "special version" would be memory friendly and twice as fast, if not faster.[/QUOTE]

Yes, please. I do have access to 32GB RAM on most of my machines so memory may not be that critical. Thanks for doing this.

 rogue 2020-06-29 00:17

[QUOTE=pxp;549321]Yes, please. I do have access to 32GB RAM on most of my machines so memory may not be that critical. Thanks for doing this.[/QUOTE]

I hacked a more optimized version of xyyxsieve (I should call it pxpsieve :smile:) that would work for your search.

Here is the command line output from a run with that input file (running on Windows):

[code]
xyyxsieve -i xyyx.in -P1e9
xyyxsieve v1.5, a program to find factors numbers of the form x^y+y^x
Sieve started: 2 < p < 1e9 with 1324 terms (78917 <= x <= 283782, 23 <= y <= 78832) (expecting 1280 factors)
p=994644191, 12.85K p/sec, 978 factors found at 70.36 sec per factor, 99.5% done. ETC 2020-06-28 19:06
Sieve completed at p=1000000009.
Processor time: 3830.22 sec. (0.03 sieving) (0.96 cores)
345 terms written to xyyx.pfgw
Primes tested: 50847536. Factors found: 979. Remaining terms: 345. Time: 3984.89 seconds.
[/code]

It was removing about 1 term per 70 seconds when it terminated. You can sieve until it takes about an hour to remove terms. I'm guessing somewhere close to 1e10. The output sieved to 1e9 is attached.

I estimate that you can fully sieve and PRP test this file of terms in about 16 days.

This was with AVX code (not AVX512), so only an AVX CPU will get that speed. If you don't have AVX, it will be slower. I estimate about 4x slower. I could probably double the non-AVX speed, but I assume that most people will run on a CPU that has AVX.

The OpenCL code has not been updated, but it could cut the time of sieving in half, thus allowing you to sieve more deeply.

 pxp 2020-06-29 17:13

 rogue 2020-06-29 20:21