Leyland Primes (x^y+y^x primes)

[storm5510]

Originally Posted by rogue

He has a special build of xyyxsieve because the way he is testing ranges is based upon decimal length of the candidates. The "out of the box" xyyxsieve is more efficient with a relatively square workspace, i.e. the range of x and y are similar in size. At one time I was working on changing xyyxsieve to be provide the "best of both worlds", but I couldn't get it to work and gave up. I might return to it someday.

The biggest challenge with xyyxsieve is that it is most efficient to sieve a very large search space once than to break that up into smaller chunks. But with a very large search space one needs a lot of memory.

On the surface, x^y + y^x does not seem all that complex. It is what surrounds it that could be very complex. Very large numbers, for one. What would qualify as a PRP candidate and what would not seems really fuzzy, to me, as each iteration would have some sort of result. I tried a few small ones with Windows Calculator. What I got was even numbers or those evenly divisible by 5. It did not take much to get into numbers larger than 1e9 either.

[xilman]

Originally Posted by storm5510

On the surface, x^y + y^x does not seem all that complex. It is what surrounds it that could be very complex. Very large numbers, for one.

That is why I drew them to people's attention. Simple representation, few clearly usable algebraic properties, observed high(-ish) density of (pseudo-)primes and a wide range of sizes.

[rogue]

Originally Posted by storm5510

On the surface, x^y + y^x does not seem all that complex. It is what surrounds it that could be very complex. Very large numbers, for one. What would qualify as a PRP candidate and what would not seems really fuzzy, to me, as each iteration would have some sort of result. I tried a few small ones with Windows Calculator. What I got was even numbers or those evenly divisible by 5. It did not take much to get into numbers larger than 1e9 either.

Removing terms with small divisors is trivial. One is basically removing terms where x^y = - y^x. The optimizations come from computing x^y from miny to maxy and y^x from minx to maxy. How much memory is needed is based upon the number of terms * number of primes tested per execution of an unrolled loop.

When I last tested a range for all 20000 < x < 30000 and 5000 < y < 30000, I still had over 3 million terms left at 15e9 after many days of sieving.

So if you consider that a GPU can do hundreds of primes at a time, one quickly sees that memory is going to be an issue. In fact the movement of data between GPU and CPU is the bottleneck. Still faster than CPU alone, but a noticeable bottleneck. I would like to try this on an Apple M1 since the CPU and GPU share memory. I have not finished the work to port to Metal as I haven't had time to work on it.

[pxp]

Originally Posted by rogue

So if you consider that a GPU can do hundreds of primes at a time, one quickly sees that memory is going to be an issue. In fact the movement of data between GPU and CPU is the bottleneck. Still faster than CPU alone, but a noticeable bottleneck. I would like to try this on an Apple M1 since the CPU and GPU share memory. I have not finished the work to port to Metal as I haven't had time to work on it.

Just a couple of observations from my Mac-centric perspective. First, for my iMacs I've always been very generous with my RAM, making sure of course that it is purchased from a seller other than Apple! User-installable RAM is not an option on a Mac mini so I have been more frugal there. My current two main (Intel) iMacs each have 128 GB installed. Second, when I ordered an M1 Mac mini (lured by an extra 2 cores) to supplement my existing Intel versions, I was very disappointed by its performance and didn't use it at all for many months. I forget if I was doing xyyxsieve or your pfgw64 for the test but it was likely xyyxsieve because I have been using all 8 cores of the M1 to test some million-digit Leyland candidates for primality and its performance is quite good (in spite of my recent finding that perhaps I shouldn't be using all the cores available). More problematic (for me) is that 3 of my most-recently-acquired Intel Mac minis (running 10.15.7), which were running as fast (or faster) than the 9 older ones (running 10.14.6) when I was doing the 300000-digits search, are running poorly in the million-digit search. I think the only change in those newer minis is a security update.

[storm5510]

Originally Posted by paulunderwood

mtsieve + OpenPFGW is my guess

I have seen ABCD and similar before. It was when I was running Riesel primes for a project four years ago. It has been so long that I do not remember how to run them. I could not get OpenPFGW to accept anything I presented to it. Then, I tried the below:

ABC2 $a^$b+$b^$a
a: from 2300 to 2320
b: from 2300 to 2320

It accepted this. It is based on a sample from a document file. It would overwrite each output line, something I prefer it not to do. I would have to study the documentation more.

Many thanks!

[rogue]

Originally Posted by storm5510

I have seen ABCD and similar before. It was when I was running Riesel primes for a project four years ago. It has been so long that I do not remember how to run them. I could not get OpenPFGW to accept anything I presented to it. Then, I tried the below:

It accepted this. It is based on a sample from a document file. It would overwrite each output line, something I prefer it not to do. I would have to study the documentation more.

Many thanks!

Use -Cverbose with pfgw. But sieving, even to a small depth, saves significant time.

[rogue]

Originally Posted by pxp

Just a couple of observations from my Mac-centric perspective. First, for my iMacs I've always been very generous with my RAM, making sure of course that it is purchased from a seller other than Apple! User-installable RAM is not an option on a Mac mini so I have been more frugal there. My current two main (Intel) iMacs each have 128 GB installed. Second, when I ordered an M1 Mac mini (lured by an extra 2 cores) to supplement my existing Intel versions, I was very disappointed by its performance and didn't use it at all for many months. I forget if I was doing xyyxsieve or your pfgw64 for the test but it was likely xyyxsieve because I have been using all 8 cores of the M1 to test some million-digit Leyland candidates for primality and its performance is quite good (in spite of my recent finding that perhaps I shouldn't be using all the cores available). More problematic (for me) is that 3 of my most-recently-acquired Intel Mac minis (running 10.15.7), which were running as fast (or faster) than the 9 older ones (running 10.14.6) when I was doing the 300000-digits search, are running poorly in the million-digit search. I think the only change in those newer minis is a security update.

From what I have read on the M1 Macs is that it isn't clear how to get applications to run on the performance cores. I want to get a PRP testing program running on it natively. Obviously gwnum is not an option for "natively". There are a couple of options, such as proth20, which I can convert to Metal (if necessary), but that is only for k*2^n+1 numbers right now.

[storm5510]

Originally Posted by rogue

Use -Cverbose with pfgw. But sieving, even to a small depth, saves significant time.

Using -Cverbose, the output is nearly identical with what it was when I was running Riesel's.

It appears in many posts I looked at above, everyone was using five-digit numbers. I will just run something smaller for an overnight test. Do they have something they are choosing them from?

Thanks!

[rogue]

Originally Posted by storm5510

Do they have something they are choosing them from?

Go to their project page.

[storm5510]

Originally Posted by rogue

Go to their project page.

Very well.

Going back through the pages, I found a Windows build of xyyxsievecl. I studied the area around page 35. It has been a bit tough to get it to run.

[rogue]

Originally Posted by storm5510

Very well.

Going back through the pages, I found a Windows build of xyyxsievecl. I studied the area around page 35. It has been a bit tough to get it to run.

The latest build of xyyxsievecl is in the mtsieve page. This assume you have an OpenCL compatible GPU. You might need to d/l drivers.