Reservations for x^y+y^x
 

This thread is to capture reservations and completed ranges per [URL="http://www.primefan.ru/xyyxf/primes.html#0"]this page[/URL]. There is another search for primes of this form, but that search is by decimal length not by range of x and y. Those reservations are not managed by this thread.

At this time all y have been tested for all x <= 13000. Note that y < x as we want x^y > y^x.

I will reserve all y for 13001 <= x <= 15000. I will also double-check from x=12501 to x = 13000.

I will do all I can to avoid stepping on the toes of the other search for primes of this form less than 100,000 decimal digits. If anything I will be double-checking their work. They will likely complete their search before I start testing the range they are working on.

The largest x^y+y^x occurs for y=x which for a given x-range occurs for the largest x in that range. Thus, the largest Leyland number up to x=13000 is 2*13000^13000, which has 53482 decimal digits. Here is a table of Leyland number decimal digits for largest x from 13000 to 30000 at intervals of 1000:

13000 53482
14000 58047
15000 62642
16000 67267
17000 71918
18000 76596
19000 81297
20000 86021
21000 90767
22000 95534
23000 100321
24000 105126
25000 109949
26000 114790
27000 119648
28000 124521
29000 129410
30000 134314

This will give you an idea of where the overlap between the two systems lies. Having checked all Leyland numbers smaller than (currently) 84734 decimal digits implies (barring errors) that I have checked all x smaller than 19728. That allows me to suggest that [URL="http://chesswanks.com/num/Kulsha(x,y).txt"]this table[/URL] of x, y values (based on Andrey Kulsha's ordering) is complete. Of course it would be nice to have verification.

[QUOTE=pxp;550590]The largest x^y+y^x occurs for y=x which for a given x-range occurs for the largest x in that range. Thus, the largest Leyland number up to x=13000 is 2*13000^13000, which has 53482 decimal digits. Here is a table of Leyland number decimal digits for largest x from 13000 to 30000 at intervals of 1000:

13000 53482
14000 58047
15000 62642
16000 67267
17000 71918
18000 76596
19000 81297
20000 86021
21000 90767
22000 95534
23000 100321
24000 105126
25000 109949
26000 114790
27000 119648
28000 124521
29000 129410
30000 134314

This will give you an idea of where the overlap between the two systems lies. Having checked all Leyland numbers smaller than (currently) 84734 decimal digits implies (barring errors) that I have checked all x smaller than 19728. That allows me to suggest that [URL="http://chesswanks.com/num/Kulsha(x,y).txt"]this table[/URL] of x, y values (based on Andrey Kulsha's ordering) is complete. Of course it would be nice to have verification.[/QUOTE]

Thanks. In the worst case scenario I will be double-checking your work, which shouldn't hurt anyone. I don't expect that to take too long after sieving.

If double-checking reveals no missed primes, then I might forego double-checking for larger x.

I've decided to take the doublecheck to x=30000. This will cover y<x for all of t those x. This could be about 6 months of work, but I don't know for certain yet because I need to do a lot of sieving.

To help me with that, I have made changes to xyyxsieve (code is committed, but exe is not on sourceforge yet) to reduce the memory usage of the program. In the previous version, a range of 1000 x can take 8 GB of memory (ouch). The changes have reduced that memory requirement by a factor of 10. Another good result of that change is a boost in speed by about 30%.

I have double-checked up to x=13000. All is good.

Sieving for x > 15000 is going much slower than anticipated. With the updates to xyyxsieve, I probably undersieved x <= 15000 by a fair amount. As soon as I finish off other PRP testing I can put more cores against the sieving.

I found a bug in xyyxsieve that causes it to remove + terms when p divides the - term. This means weeks of sieving is lost. Fortunately it only means that I need to retest any terms accidentally removed for x < 14000, but I still need to resieve just to find out what I didn't test that should have been tested. On the plus side this only impacts me as the build with this bug is not in the latest distribution of mtsieve.

The bug was introduced when I changed xyyxsieve to support only + or -, but not both concurrently as the older versions support that.

[QUOTE=rogue;552778]I have made changes to xyyxsieve (code is committed, but exe is not on sourceforge yet) to reduce the memory usage of the program. In the previous version, a range of 1000 x can take 8 GB of memory (ouch). The changes have reduced that memory requirement by a factor of 10. Another good result of that change is a boost in speed by about 30%.[/QUOTE]

You had previously provided me with an OS X version of this ([URL="https://www.mersenneforum.org/showthread.php?t=19347&page=35"]xyyxsieve.7z[/URL]). As I am currently entering a phase where I will be sieving millions of large numbers, a 30% boost looks pretty good right now. I had started a sieve to 5e9 on [URL="http://chesswanks.com/num/a094133.txt"]interval #21[/URL] back on August 12 and it is currently at 8% with an ETC of mid-January. Ouch!

[QUOTE=pxp;554924]You had previously provided me with an OS X version of this ([URL="https://www.mersenneforum.org/showthread.php?t=19347&page=35"]xyyxsieve.7z[/URL]). As I am currently entering a phase where I will be sieving millions of large numbers, a 30% boost looks pretty good right now. I had started a sieve to 5e9 on [URL="http://chesswanks.com/num/a094133.txt"]interval #21[/URL] back on August 12 and it is currently at 8% with an ETC of mid-January. Ouch![/QUOTE]

How many terms? How many distinct x? How many distinct y?

2020-08-12 22:17:06: Sieve started: 3 < p < 5e9 with 7448612 terms (29963 <= x <= 453605, 2 <= y <= 30453) (expecting 7082193 factors). I am currently at p=418504277 with 7114884 factors found.

[QUOTE=pxp;554958]2020-08-12 22:17:06: Sieve started: 3 < p < 5e9 with 7448612 terms (29963 <= x <= 453605, 2 <= y <= 30453) (expecting 7082193 factors). I am currently at p=418504277 with 7114884 factors found.[/QUOTE]

With such a large range of x and y, the program I provided is likely faster than the current version that I am running. You can try the attached, but I make no promises that it will be faster. Note that the ABC header format is "ABC $a^$b+$b^$a" or "ABC $a^$b-$b^$a" with no +1 or -1 on each line. I don't recall the format that was supported by what I provided last month.

Note that I am sieving all y < 40000 for x <= 40000.

Also note that it crashes upon shutdown, but that is only after it has written the output file and closed it. I haven't dug into the cause yet. I suspect I'm freeing memory that has not been allocated.

Thank you. As I had just finished interval #13, I was going to have a run-off between the two versions. So I interrupted my running version, took a duplicated output file and removed the +1s for the new ABC format, placed that file in the folder containing the new xyyxsieve on my other computer, and ran it. Unfortunately it terminated with a "Segmentation fault: 11".

[QUOTE=pxp;554974]Thank you. As I had just finished interval #13, I was going to have a run-off between the two versions. So I interrupted my running version, took a duplicated output file and removed the +1s for the new ABC format, placed that file in the folder containing the new xyyxsieve on my other computer, and ran it. Unfortunately it terminated with a "Segmentation fault: 11".[/QUOTE]

It is possible that you do not have enough memory. The version of software I provided is not designed to support very large ranges of x. I suggest you continue with the version I posted a few weeks ago.

After I restarted the interrupted run (using its output file as my new input) the program began with an ETC of September 1. That's quite a change from the previous mid-January 2021. Now those early ETC calculations aren't firm but I wonder now if the initial file size somehow skews the ETC guess. As I have a handful of other sieves going I will interrupt a couple of those to see if I get a similar advance in ETC dates using the size-reduced output files as new inputs.

[QUOTE=pxp;554998]Now those early ETC calculations aren't firm but I wonder now if the initial file size somehow skews the ETC guess. As I have a handful of other sieves going I will interrupt a couple of those to see if I get a similar advance in ETC dates using the size-reduced output files as new inputs.[/QUOTE]

I am seeing much earlier ETC dates on restarted interruptions. Perhaps a better guess than file size being the cause is multi-core implementation. As all of my sieves are run as a single process on a 6-core machine, I use -W6. Perhaps the ETC does not take that performance improvement into account.

[QUOTE=pxp;555009]I am seeing much earlier ETC dates on restarted interruptions. Perhaps a better guess than file size being the cause is multi-core implementation. As all of my sieves are run as a single process on a 6-core machine, I use -W6. Perhaps the ETC does not take that performance improvement into account.[/QUOTE]

The ETC is based upon when the sieving started compared to where it currently is and is based upon the last prime that has been successfully sieved. Various things impact this calculation including the type of sieve and the number of threads. Regarding the "type of sieve", sieves such as xyyxsieve and gcwsieve start slow, but "p/sec" increases as terms are removed. This means that each "chunk" takes longer for small p than for large p. This causes the ETC to be reduced as p increases. I could change this, but I haven't thought much about it since so few sieves are impacted by it.

I have verified all PRPs for x <= 14000. The range for 14000 < x <= 20000 has about 1.5 million terms in it. I will be starting on that soon.

[QUOTE=rogue;557236]I have verified all PRPs for x <= 14000. The range for 14000 < x <= 20000 has about 1.5 million terms in it. I will be starting on that soon.[/QUOTE]

Verification done thru x <= 15000. Estimate of about 7 weeks to finish the double check for x <= 20000.

I made an interesting observation when looking at primes/PRPs of this form. The last column is the number of primes in the range. Note the relatively even distribution despite the geometric growth of terms in the range (approximately (max x)^2). Is that expected or is that unusual?

The numbers for x > 15000 have not been verified yet.

[code]
0 <= x < 1000 87
1000 <= x < 2000 87
2000 <= x < 3000 92
3000 <= x < 4000 80
4000 <= x < 5000 80
5000 <= x < 6000 72
6000 <= x < 7000 69
7000 <= x < 8000 80
8000 <= x < 9000 79
9000 <= x < 10000 61
10000 <= x < 10000 63
10000 <= x < 11000 75
11000 <= x < 12000 63
12000 <= x < 13000 70
13000 <= x < 14000 67
14000 <= x < 15000 68
15000 <= x < 16000 66
16000 <= x < 17000 50
17000 <= x < 18000 71
[/code]

Here are updates based upon prp's searching (barring mistakes in my counting):

[code] 0 <= x < 1000 87
1000 <= x < 2000 87
2000 <= x < 3000 92
3000 <= x < 4000 80
4000 <= x < 5000 80
5000 <= x < 6000 72
6000 <= x < 7000 69
7000 <= x < 8000 80
8000 <= x < 9000 79
9000 <= x < 10000 61
10000 <= x < 10000 63
10000 <= x < 11000 75
11000 <= x < 12000 63
12000 <= x < 13000 70
13000 <= x < 14000 67
14000 <= x < 15000 68
15000 <= x < 16000 66
16000 <= x < 17000 50
17000 <= x < 18000 71
18000 <= x < 19000 72
19000 <= x < 20000 79
20000 <= x < 21000 62
21000 <= x < 22000 79
22000 <= x < 23000 71
23000 <= x < 24000 73
24000 <= x < 25000 56
25000 <= x < 26000 47
26000 <= x < 27000 33[/code]

Note that for x > 24000 the distribution changes, but that is because those ranges are not fully tested. I'm not even certain of the entire search space for x < 24000 has been fully tested. Every x < 23000 looks like it has been tested, but I can't speak for x > 23000 as there appear to be some gaps (from my perspective).

[QUOTE=rogue;557866]Note that for x > 24000 the distribution changes, but that is because those ranges are not fully tested. I'm not even certain of the entire search space for x < 24000 has been fully tested. Every x < 23000 looks like it has been tested, but I can't speak for x > 23000 as there appear to be some gaps (from my perspective).[/QUOTE]

You are correct. By mid-October I will have finished interval #16 which will guarantee x < 24000. To get to x < 25000 I will need to finish interval #17, which I haven't started yet. My current long-term goal is 150000 decimal digits which will bring this up to x < 33000.

[QUOTE=pxp;557883]You are correct. By mid-October I will have finished interval #16 which will guarantee x < 24000. To get to x < 25000 I will need to finish interval #17, which I haven't started yet. My current long-term goal is 150000 decimal digits which will bring this up to x < 33000.[/QUOTE]

Sieving is really slow for 20000 < x <= 40000. There are over 10m terms remaining at a little over 1e9 and it to take me months to sieve deeply enough using 6 cores. The problem is that xyyxsieve needs a lot of memory to sieve the range efficiently (over 10GB for 6 workers), but the memory access gets expensive. I tried adding a prefetch as that should help with speed, but my initial attempts have hurt performance. I'm sure that is the key, but I very likely am doing something wrong. With 6 cores I am only testing about 30 p per second. I could possibly gain some speed by looking at x with few y terms and avoid building a power table for those x in memory. The same could be said for y with few x terms. I'm not certain if there are enough x or y with few terms that sieving could benefit from it.

As soon as I complete for x <= 20000, I will peel off ranges of of y in groups of 1000 from the 10m data set. Those are the smaller terms from the big range and as I pull them out sieving should pick up a little bit of speed.

Actually there are 68 primes for 15000 <= x < 16000. I miscounted above.

The range for x < 16000 has now been double-checked. No missing primes/PRPs.

[QUOTE=pxp;555009]I am seeing much earlier ETC dates on restarted interruptions.[/QUOTE]

Unfortunately, this fix is no longer working well on my now much larger input files. The interruptions (after about a day of sieving) run into an error that has one or more workers not responding within a ten-minute default and xyyxsieve aborts the writing of the final output file. The existing output file is smaller than the input file but I have been afraid to use it because I fear that it has been contaminated by that final aborted write attempt.

One of the problems here was that I was not letting it run long enough. The existing output file might have had "// Sieved to 5" which confused me because the run was at p=600000+. A couple of times I even had a "// Sieved to 0" which strikes me as nonsensical. Clearly this is all about when exactly the program chooses to write an output and how long it actually takes to write that output. And I understand now that it is the writing of that output for very large files that is driving the ETC dates unrealistically into the distant future.

An unfinished example is a run on interval #18's almost 28 million term input file (406 MB) started on September 26:

[CODE]./xyyxsieve -i18.ini -o18.txt -W4 -p3 -P1e7[/CODE]

which, as I write, is at:

[CODE]p=4798627, 2.361 p/sec, 24100965 factors found at 0.000 f/sec, 48.0% done. ETC 2020-10-07 07:04[/CODE]

The current output file is sieved to 1481 and is down to 57 MB. When I get to the end I think that I will still run into this ten-minute unresponsive-worker abort of the final output update but the existing output file at that time should be sieved to a large enough number to be usable. Should I worry that such a file may have been corrupted by that final unsuccessful write attempt? What if the aborted file-write caused the file that is there at the finish to be missing a whole bunch of terms? That would directly impact the possibility of my not finding [I]all[/I] PRPs in that interval.

The program will update the output file once every 60 minutes. The "Sieved to" value in that file is the largest prime that the program can conclusively state has been successfully sieved to with no gaps.

My recommendation is to sieve with a single thread to 1e4 or 1e5 to knock out most of the candidates. Then start again on the output file with multiple threads. You should also consider using -w1e4 to reduce the number of primes per check. This also means that ^C will terminate the program faster. It might still take many minutes due to the number of terms, but it will terminate.

The ETC dates are far into the future because the time to sieve the first chunk takes a really long time and the program extrapolates based upon that. The ETC will come closer to the present as the number of terms is reduced. That is why I suggest sieving to 1e4 or 1e5 with a single worker before running again with multiple threads.

[QUOTE=rogue;558553]You should also consider using -w1e4 to reduce the number of primes per check. This also means that ^C will terminate the program faster. It might still take many minutes due to the number of terms, but it will terminate.[/QUOTE]

According to the xyyxsieve help file the default for -w is 1e4, so that is what I have (unknowingly) been using. Trying 1e3 is "out of range". What is the point of larger -w arguments? I will guess faster processing but perhaps at the expense of RAM. That is not for me an issue as I have 32 GB on all of my machines and I have not found either xyyxsieve or pfgw take any advantage of it.

I tried:

[CODE]mm4:rogue1 pxp$ ./xyyxsieve -i19.ini -o19.txt -w1e4 -p3 -P1e4
xyyxsieve v1.5, a program to find factors numbers of the form x^y+y^x
Sieve started: 3 < p < 1e4 with 17782120 terms (27440 <= x <= 425055, 2 <= y <= 28701) (expecting 15661063 factors)
p=0, 0.000 p/sec, 3187205 factors found at 176.5 f/sec, 0.0% done.
1 workers didn't stop after 10 minutes[/CODE]

So the single thread and -P1e4 made no difference.

What I am going to do is multi-thread these runs to -P1e9 and after several days just rescue (move elsewhere) whatever output file is there and then kill the run. Also, in the future, I think I will do some small sieving in Mathematica prior to creating the ABC files. I had been reluctant to do this initially because I figured xyyxsieve would be just so much faster.

With so many candidates, it will take a long time to get to 1e4. Yes -w must be at least 1e4.

The version of xyyxsieve that I gave to you won't benefit when adding more candidates. You might as well divide the input to smaller files and sieve them.

[QUOTE=rogue;558553]The program will update the output file once every 60 minutes.[/QUOTE]

I am looking at this now. One of my runs was updated at 2:48 pm today: sieved to 11 (149.2 MB); then at 3:49 pm: sieved to 13 (142.2 MB); then at 4:50 pm: sieved to 13 (140.3 MB); then at 5:51 pm: sieved to 17 (136.3 MB); then at 6:52 pm: sieved to 17 (132.7 MB).

At this point xyyxsieve has:

[CODE]Sieve started: 3 < p < 1e9 with 22133879 terms (30455 <= x <= 476849, 2 <= y <= 31873) (expecting 20960485 factors)
p=243011, 0.098 p/sec, 13031312 factors found at 5.358 f/sec, 0.0% done. ETC 2032-08-29 10:30[/CODE]

Note that p is past 243000. It has already found 13 million of an expected 21 million factors. Checking the 6:52 pm file, has it just over 9 million terms in it which is exactly in line with the 13 million factors found. Most troubling are the sieved-to numbers: 11, 13, 13, 17, 17. All the while p has been at 200000+. My guess is that the sieved-to numbers are incorrect. Should they not be where p is at?

[QUOTE=pxp;558894]Most troubling are the sieved-to numbers: 11, 13, 13, 17, 17. All the while p has been at 200000+. My guess is that the sieved-to numbers are incorrect. Should they not be where p is at?[/QUOTE]

I don't understand.

When p=3 and one has divided all initial candidates by 3, one has sieved to 3. When p=5 and one has divided all remaining candidates by 5, one has sieved to 5. When p=7 and one has divided all remaining candidates by 7, one has sieved to 7. Is that not correct or the way the program works?

[QUOTE=pxp;558958]When p=3 and one has divided all initial candidates by 3, one has sieved to 3. When p=5 and one has divided all remaining candidates by 5, one has sieved to 5. When p=7 and one has divided all remaining candidates by 7, one has sieved to 7. Is that not correct or the way the program works?[/QUOTE]

That is correct. I did not understand this:

[quote]Most troubling are the sieved-to numbers: 11, 13, 13, 17, 17. All the while p has been at 200000+. My guess is that the sieved-to numbers are incorrect. Should they not be where p is at?[/quote]

Are you suggesting that many p were skipped (in other words the value for "sieved to" is wrong)? Are you suggesting that some factors were missed for p that were tested? Is there some other issue? I just don't understand your comments.

As per my examples, when p = n has been reached, I expect the output file to be sieved to n (and you have said that my expectation is correct). Instead, the program is saying p ~ 200000 but the output file is [I]not[/I] sieved to ~200000 but, rather, to 17. An hour later, p (supposedly, if the program value is to be believed) has advanced by thousands but the new output sieved-to number is still 17. There is no correspondence, so yes, either the sieved-to-number is wrong or the "p=" number in the console is wrong. I can't fathom either possibility which is why I had rather expected you to say that my understanding of the correspondence was [I]incorrect[/I].

[QUOTE=pxp;559075]As per my examples, when p = n has been reached, I expect the output file to be sieved to n (and you have said that my expectation is correct). Instead, the program is saying p ~ 200000 but the output file is [I]not[/I] sieved to ~200000 but, rather, to 17. An hour later, p (supposedly, if the program value is to be believed) has advanced by thousands but the new output sieved-to number is still 17. There is no correspondence, so yes, either the sieved-to-number is wrong or the "p=" number in the console is wrong. I can't fathom either possibility which is why I had rather expected you to say that my understanding of the correspondence was [I]incorrect[/I].[/QUOTE]

I see what you are saying. The issue is with the build that you have. There was an issue where it was not choosing the correct value for display on the screen if running multiple threads. The file is to be believed.

The range for x < 17000 has now been double-checked. No missing primes/PRPs.

The range for x < 18000 has now been double-checked. No missing primes/PRPs.

So the range from 17000 to 17999 is an outlier with only 50 PRPs. Interesting.

I started sieving a month ago for all x where 30000 <= x < 40000 (and y < x). Sieving is very slow for such a large range. I will not continue sieving this range or test it at this time. If someone else is interested, please let met know. I will post the file of terms if there is interest. It is only sieved to about 2.6e9 and still has 5.6 million terms in the range.

I am still sieving for 20000 <= x < 30000 (and all y < x). This is also going very slowly. I doubt it will be sieved deeply enough before I finish for x < 20000, but I can split off small y (since those tests are faster) and continue sieving. It is really hard to estimate how much time it will take to test that range because test times vary considerably. It will have around 4 million terms in it. I don't know how far I will test it, but I want to test to x < 25000.

The range for x < 19000 has now been double-checked. No missing primes/PRPs. There are 71 primes/PRPs in that range. I had miscounted in a table in a previous post.

Actually there are 78 primes for 19000 <= x < 20000. I miscounted above.

All x < 20000 has now been double-checked. No missing primes/PRPs.

My tactic for testing 20000 <= x < 30000 is a little different due to speed of sieving. I am testing all x in that range at once, but subdividing by y as PRP tests for smaller y are faster. I am testing for y <= 1000 while sieving for y > 1000 continues.

I have confirmed all known PRPs for x < 30000 where y < 5000. Nothing was missed by previous searchers. Since nothing was missed I am going to discontinue the double-check.

For those who are still searching other ranges for x < 30000, the attached file, sieved to 13896059123, has all x/y pairs that I have not tested for x < 30000. You can use this file in one of two ways. First, see if you tested the x/y pairs that are in this file for the ranges you have tested. Assuming that you haven't sieved as deeply as I have, then this file could have x/y pairs that you didn't test. Second, if you are searching x < 30000 and haven't sieved as deeply as I have, you can use this file to start testing those ranges sooner.