mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > XYYXF Project

Reply
 
Thread Tools
Old 2020-06-27, 14:03   #353
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

22·41 Posts
Default

Quote:
Originally Posted by rogue View Post
Send me one of your lists and I'll sieve with xyyxsieve.
Did you mean (for example) my original 17632 Leyland number pairs list that I reduced to 1324 candidate terms? 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.
pxp is offline   Reply With Quote
Old 2020-06-27, 15:45   #354
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×52×59 Posts
Default

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.
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
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.
rogue is offline   Reply With Quote
Old 2020-06-28, 02:31   #355
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

101001002 Posts
Default

Quote:
Originally Posted by rogue View Post
pfgw will likely be faster ...
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.
pxp is offline   Reply With Quote
Old 2020-06-28, 13:23   #356
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

590010 Posts
Default

Quote:
Originally Posted by pxp View Post
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.
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 is offline   Reply With Quote
Old 2020-06-28, 13:51   #357
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×52×59 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2020-06-28, 23:48   #358
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

22·41 Posts
Default

Quote:
Originally Posted by rogue View Post
From there you can execute pfgw64 by typing "./pfgw64" ...
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)
Under an hour, compared to the 6 hours it had previously taken in Mathematica. I'm blown away!
pxp is offline   Reply With Quote
Old 2020-06-28, 23:52   #359
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

22·41 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
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.
pxp is offline   Reply With Quote
Old 2020-06-29, 00:17   #360
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22·52·59 Posts
Default

Quote:
Originally Posted by pxp View Post
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.
I hacked a more optimized version of xyyxsieve (I should call it pxpsieve ) 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.
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.
rogue is offline   Reply With Quote
Old 2020-06-29, 17:13   #361
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

22×41 Posts
Default

Is this ready? Where do I download?
pxp is offline   Reply With Quote
Old 2020-06-29, 20:21   #362
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×52×59 Posts
Default

Quote:
Originally Posted by pxp View Post
Is this ready? Where do I download?
Do you want a Windows build or OS X build? Or do you want the source so that you can build it on your own?
rogue is offline   Reply With Quote
Old 2020-06-29, 21:03   #363
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

22·41 Posts
Default

I would like a ready-to-run OS X build.
pxp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Leyland Primes: ECPP proofs Batalov XYYXF Project 16 2019-08-04 00:32
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
On Leyland Primes davar55 Puzzles 9 2016-03-15 20:55
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 03:40.

Mon Sep 21 03:40:35 UTC 2020 up 11 days, 51 mins, 0 users, load averages: 1.17, 1.38, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.