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

[Batalov]

Originally Posted by rogue

I don't know why --platform doesn't work so I need to investigate that, but -f should now work to change the platform (although I haven't tested it).

--platform still doesn't work
Neither does -f1

$ ./xyyxsievecl64.exe -f1 -x100 -X200 -y3000 -Y4000 -P2e6 -t2 -s3000 -S+ -b32 -oxyyx.pfgw -f01
xyyxsievecl v1.0.3, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    50551 because the term is even
    9478 because x and y have a common divisor
    28375 because the term is divisible by a prime < 100
Platform 0 has no available devices.  Here is a list of platforms and devices:List of available platforms and devices
Platform 0 is a Intel(R) Corporation Intel(R) OpenCL, version OpenCL 1.2
   No devices
Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.2 CUDA 8.0.5
   Device 0 is a NVIDIA Corporation GeForce GTX 570
$ ./xyyxsievecl64.exe -f1 -x100 -X200 -y3000 -Y4000 -P2e6 -t2 -s3000 -S+ -b32 -oxyyx.pfgw  --platform=1
xyyxsievecl v1.0.3, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    50551 because the term is even
    9478 because x and y have a common divisor
    28375 because the term is divisible by a prime < 100
Platform 0 has no available devices.  Here is a list of platforms and devices:List of available platforms and devices
Platform 0 is a Intel(R) Corporation Intel(R) OpenCL, version OpenCL 1.2
   No devices
Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.2 CUDA 8.0.5
   Device 0 is a NVIDIA Corporation GeForce GTX 570

[rogue]

Try this one. I found a bug where the selected platform was being reset to 0.

[pxp]

L(13537,3948)

[Batalov]

Originally Posted by rogue

Try this one. I found a bug where the selected platform was being reset to 0.

Thanks!
This binary works fine for "+" side but does nothing for the "-" side:

$ ./xyyxsievecl64.exe -S- -x 10 -X 20 -y 4000 -Y 70000 -p 3 -P 1e13 -oxy-yx-50m.out -b32 -s3000 -f1
xyyxsievecl v1.0.4, a GPU program to find factors numbers of the form x^y+y^x
Switching x and y for optimization
Quick elimination of terms info (in order of check):
    0 because the term is even
    0 because x and y have a common divisor
    0 because the term is divisible by a prime < 100
Sieve started: (cmdline) 3 <= p < 10000000000000 with 0 terms
(and then works really hard though it has nothing in the sieve!!)
 p=3166487141, 6.035K p/sec, 0 factors found at 0 secs/factor, 0.35 CPU cores, 0.0% done. ETA 07 May 14:02

In comparison:
$ ./xyyxsievecl64.exe -S+ -x 10 -X 20 -y 4000 -Y 70000 -p 3 -P 1e13 -oxy-yx-50p.out -b32 -s3000 -f1
xyyxsievecl v1.0.4, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    363006 because the term is even
    64532 because x and y have a common divisor
    233691 because the term is divisible by a prime < 100
Sieve started: (cmdline) 3 <= p < 10000000000000 with 64782 terms
1078739 | 10^25157+25157^10
1090423 | 10^14839+14839^10
1005593 | 11^5532+5532^11
1048891 | 10^60093+60093^10
1039111 | 11^13738+13738^11
.......

?

[rogue]

This should fix that. I had a piece of code that tried to prevent the ranges of x and y from overlapping. It was coded incorrectly, so I removed it. It will be up to the user to not do something stupid.

[Batalov]

It seems to work now, thanks!

[Batalov]

Further tests show that something is not right, though.
Debug example:

$ ./xyyxsievecl64.exe -x11 -X11 -y166212 -Y166212 -S- -f1 -P1e10
xyyxsievecl v1.0.5, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
    0 because the term is even
    0 because x and y have a common divisor
    1 because the term is divisible by a prime < 100
Sieve started: (cmdline) 0 <= p < 10000000000 with 0 terms
CTRL-C accepted.  Please wait for threads to completed.
Thread 1 has completed 0 of 2 iterations
Sieve interrupted: 3 <= p < 10000000000  529920 primes tested
Clock time: 6.46 seconds at 82001 p/sec.  Factors found: 0
Processor time: 2.40 sec. (0.09 init + 2.31 sieve).
Seconds spent in CPU and GPU: 0.37 (cpu), 11.66 (gpu)
Percent of time spent in CPU vs. GPU: 3.06 (cpu), 96.94 (gpu)
CPU/GPU utilization: 0.37 (cores), 1.00 (devices)
Percent of GPU time waiting for GPU: 40.23

1. 11^166212-166212^11 is not divisible by small factor (one can check with PFGW!) yet it is removed
2. Why does the sieve proceed to sieve _after_ it knows that it has 0 terms in the sieve?!

A possible "answer" to issue #1 is that 29 | 11^166212[COLOR=Red][B]+[/B][/COLOR]166212^11, which of course doesn't matter for the [COLOR=Red]-[/COLOR] side.

[rogue]

I appreciate your testing Serge. The attached should address both of those issues. The issue with finding the factor < 100 was due to a numeric overflow because one of your x/y values exceeded 2^15.5. That is now fixed. I don't know if anyone has been using this program for x/y that are that large, but if so, then they might need to retest their range again.

[Batalov]

Thank you.
I am in the process of testing a chunk of data and will compare to Multisieve'd chunk (which is also known to be suspect; I think you wrote about that). It is by running this comparison and drilling down to separate examples of mismatches that I have found that previous example (only one of many). I will report after the sieve progresses far enough that it will be expected to produce just a subset of what Multisieve produced.

[rogue]

Originally Posted by Batalov

Thank you.
I am in the process of testing a chunk of data and will compare to Multisieve'd chunk (which is also known to be suspect; I think you wrote about that). It is by running this comparison and drilling down to separate examples of mismatches that I have found that previous example (only one of many). I will report after the sieve progresses far enough that it will be expected to produce just a subset of what Multisieve produced.

Unfortunately MultiSieve will miss factors and xyyxsievecl will remove candidates incorrectly. Fortunately xyyxsievecl will log factors so you can double-check those with pfgw.

[Batalov]

Alas, xyyxsievecl64.exe v 1.0.6 also behaves unexpectedly.

The log file is large but upon analysis only contains factors up to a few million (they are not sorted by p, which is fine - this is a multi-threaded application), and then factors above ~3.1e9 and if the application is left to its own devices, p very slowly grows (no more huge leaps forward). Further analysis confirms that factors are valid, but that no sieving occurred between 3932129 < p < 3162375959 . For that, I have compared earlier smaller sieve (done with Multisieve) and checked the mismatches: the Multisieve'd file had a few lines more (and they indeed had rare factors above 3.1e9) but xyyxclsieve'd file had many more lines which upon check with GP have relatively small factors in the 3932129 < p < 3162375959 gap.

Here is my detailed post-mortem:

./xyyxsievecl64.exe -S- -x 10 -X 50 -y 29000 -Y 300000 -p 3 -P 1e13 -oxy-yx-50m.out -b32 -s3000 -f1

... stdout after a few hours looked like
Thread 2 has completed 699614 of 993263 iterations
3418687241 | 288888^11-11^288888
3418947209 | 254946^13-13^254946
  p=3418739089, 322.6 p/sec, 994311 factors found at 23 secs/factor, 0.25 CPU cores, 0.0% done. ETA 28 Jun 06:33
3419618533 | 41862^37-37^41862
3419563187 | 64583^12-12^64583
3419586013 | 151731^34-34^151731
Thread 2 has completed 708625 of 993263 iterations
  p=3419415253, 356.0 p/sec, 994314 factors found at 22 secs/factor, 0.25 CPU cores, 0.0% done. ETA 30 Jun 22:58
3420401519 | 142459^20-20^142459
CTRL-C accepted.  Please wait for threads to completed.
Thread 1 has completed 645563 of 993263 iterations
3420383999 | 190741^20-20^190741
Thread 2 has completed 165122 of 993263 iterations
2 threads didn't stop after 10 minutes
   Thread 0: Worker Status: 4  Sieve Status: 3
   Thread 1: Worker Status: 4  Sieve Status: 3

$ head xyyxsieve.log
5 | 29001^16-16^29001
29 | 29001^20-20^29001
5 | 29001^26-26^29001
31 | 29001^38-38^29001
5 | 29001^46-46^29001
3 | 29002^11-11^29002
3 | 29002^13-13^29002
7 | 29002^15-15^29002
3 | 29002^19-19^29002
13 | 29002^21-21^29002
...
$ awk '$1<14000000' xyyxsieve.log |sort -n |tail
3931393 | 45746^37-37^45746
3931481 | 114715^14-14^114715
3931687 | 158045^32-32^158045
3931687 | 223748^29-29^223748
3931721 | 218282^35-35^218282
3931801 | 215368^39-39^215368
3931861 | 255704^19-19^255704
3932063 | 112768^27-27^112768
3932119 | 124718^39-39^124718
3932129 | 37965^44-44^37965

# then immediate leap to ...

$ awk '$1>4000000' xyyxsieve.log |sort -n |head
3162375959 | 246854^25-25^246854
3162378119 | 164292^17-17^164292
3162418769 | 209003^44-44^209003
3162425921 | 173201^50-50^173201
3162563959 | 286509^20-20^286509
3162599239 | 100591^20-20^100591
3162642233 | 96480^43-43^96480
3162729233 | 163034^41-41^163034
3162784357 | 56157^26-26^56157
3163215511 | 268353^26-26^268353


$ cat  xyyxsieve.ckpt
App: 3 3417388769 10000000000000 23823360 33787046877 24488718148540015 67113612774 132938061532
XYYXSieveApp: 994306
$

# Let's check validity of factors with GP

======================tr.pl======================
#!/usr/bin/perl -w

while (<>)  {
  s/\s+$//;
  /(\d+) \| (\d+)\^(\d+)-(\d+)\^(\d+)/;
  die if ($2 ne $5 || $3 ne $4);
  print "if(Mod($2,$1)^$3!=Mod($3,$1)^$2,print(\"$_\"))\n";
}
======================tr.pl======================

$ head xyyxsieve.log |perl tr.pl
if(Mod(29001,5)^16!=Mod(16,5)^29001,print("5 | 29001^16-16^29001"))
if(Mod(29001,29)^20!=Mod(20,29)^29001,print("29 | 29001^20-20^29001"))
if(Mod(29001,5)^26!=Mod(26,5)^29001,print("5 | 29001^26-26^29001"))
if(Mod(29001,31)^38!=Mod(38,31)^29001,print("31 | 29001^38-38^29001"))
if(Mod(29001,5)^46!=Mod(46,5)^29001,print("5 | 29001^46-46^29001"))
if(Mod(29002,3)^11!=Mod(11,3)^29002,print("3 | 29002^11-11^29002"))
if(Mod(29002,3)^13!=Mod(13,3)^29002,print("3 | 29002^13-13^29002"))
if(Mod(29002,7)^15!=Mod(15,7)^29002,print("7 | 29002^15-15^29002"))
if(Mod(29002,3)^19!=Mod(19,3)^29002,print("3 | 29002^19-19^29002"))
if(Mod(29002,13)^21!=Mod(21,13)^29002,print("13 | 29002^21-21^29002"))
$ head xyyxsieve.log |perl tr.pl |gp -q

$ cat xyyxsieve.log |perl tr.pl |gp -q

#--> all factors are valid