Leyland Primes (x^y+y^x primes)
Placeholder for x[SUP]y[/SUP]+y[SUP]x[/SUP] prime search reservations.
Contact [URL="http://www.mersenneforum.org/member.php?u=1540"]XYYXF[/URL] to [URL="http://www.primefan.ru/xyyxf/primes.html#0"]reserve a range[/URL]. Multisieve is one of the sieve programs capable of sieving this form. 
Yafu can sieve this form too.

It can? :ermm:

:missingteeth::ick:
Sorry, I don't laugh at any of you. It is just about the situation, I expected all in the world but didn't expect Ben's reply to this, in this way! [edit: if some guest read this, maybe they don't know, Ben is yafu's author]. I can't stop laughing. 
[QUOTE=bsquared;373350]It can? :ermm:[/QUOTE]
You mean it can't? I thought Yafu did everything. :smile: I stand corrected  Yafu can factor this form via SNFS. 
[QUOTE=swellman;373354]You mean it can't? I thought Yafu did everything. :smile:
I stand corrected  Yafu can factor this form via SNFS.[/QUOTE] Err, well, yes, of course it can do everything, except for LaurV's loops and ifs :smile: Yep, you were probably thinking of SNFS factorization. 
Well, of course, sieving can be done with almost any program (including your own). But the question is how fast can it sieve. Multisieve is good.
[U]A worked example[/U]: 1. Get [URL="http://home.roadrunner.com/~mrodenkirch/home/MultiSieve.html"]Multisieve[/URL] and PFGW 2. Start, select x^y+y^x mode, select "+", set up some names for outputs, e.g. "xyyx200.out" and "xyyx200.log"; set up limits above previously searched: e.g. x from 200 to 200, y from 20001 to 30000 3. Sieve, after a while, stop (e.g. at 1020s per candidate) 4. Run pfgw on the "xyyx200.out" file (with f0 l) 5. ... 6. PROFIT! [SPOILER]e.g. 200^20373+20373^200 is a (new) PRP[/SPOILER] 7. Submit to [URL="http://www.primenumbers.net/prptop/submit.php"]PRP top[/URL] 
[QUOTE=Batalov;373363]e.g. x from 200 to 200, y from 20001 to 30000[/QUOTE]Conventionally x is always greater than y, and it's also recommended to test all y's for a given x :)
So it's better to take e.g. x from 12501 to 13000, y from 2001 to 12999 :) 
Multisieve reversed that order (because x[SUP]y[/SUP] > y[SUP]x[/SUP], for 3<=x<y, and because it sieves for x[SUP]y[/SUP] +/ y[SUP]x[/SUP], so it would be convenient to have a positive number). It was an example of setting up Multisieve. Multisieve will require x<y.
Let's start the fun? I will run the [2000140000, 11200] range. Found six new PRPs so far, while warming up. 
OK, [url]http://xyyxf.at.tut.by/primes.html#ranges[/url] is updated. But I still hope someone will decrease the number of steps y>10, y>200, y>1000, y>2000 :)
E.g. it's possible to take [1500120000, 10012000]. 
I haven't touched MultiSieve in years. It's good to know that some people still have use for it. After looking at the code (talk about a blast from the past), I think it would be easy to convert this sieve to OpenCL since it doesn't use a discrete log. An OpenCL version might 100x faster.

[QUOTE=Batalov;373293]Placeholder for x[SUP]y[/SUP]+y[SUP]x[/SUP] prime search reservations.
Contact [URL="http://www.mersenneforum.org/member.php?u=1540"]XYYXF[/URL] to [URL="http://xyyxf.at.tut.by/primes.html#0"]reserve a range[/URL]. Multisieve is one of the sieve programs capable of sieving this form.[/QUOTE] Now if Paul would like to take the time to update his [URL="http://www.leyland.vispa.com/numth/primes/xyyx.htm"]webpage[/URL]... ...or someone else could take ownership. [COLOR="Blue"]EDIT (S.B.): That's exactly what Andrey did a few years ago: [url]http://xyyxf.at.tut.by/primes.html#0[/url][/COLOR] 
[2000140000, 11200] range is done. One PRP I had found two years ago, and now, the rest:
[CODE]11^36442+36442^11, 37951(decimal digits) (2012) 33^21262+21262^33, 32287 63^20018+20018^63, 36020 76^24787+24787^76, 46620 92^32907+32907^92, 64623 98^27819+27819^98, 55394 105^34684+34684^105, 70103 117^26870+26870^117, 55573 128^29007+29007^128, 61124 128^32001+32001^128, 67433 129^28468+28468^129, 60085 131^31870+31870^131, 67478 143^39070+39070^143, 84209 157^29934+29934^157, 65733 163^26530+26530^163, 58690 181^22300+22300^181, 50347 200^20373+20373^200, 46879 [/CODE] Submitted to PRP top, they will show up in a few days. 
[QUOTE=XYYXF;373379]E.g. it's possible to take [1500120000, 10012000].[/QUOTE]
Ok. Consider this range done, too. ;) 
FWIW, the result of sieving the range [1250115000, 200115000] to 1657571 (which took a few hours on a core)
[url]https://www.dropbox.com/s/5plhnqg5hwqtbn8/xyyx.7z[/url] As a rough estimate: 700,000 candidates (guess of how many will remain after sieving; currently 720,880 remaining) at 40 seconds (timings for PFGW tests ranged from 26 to 58 seconds) per candidate per core makes this range an 80 day job for a quad core Haswell. I don't want to make that much of a commitment right now, but someone can use my sieve file as a starting point. :smile: 
[QUOTE=XYYXF;373379]OK, [url]http://xyyxf.at.tut.by/primes.html#ranges[/url] is updated. But I still hope someone will decrease the number of steps y>10, y>200, y>1000, y>2000 :)
E.g. it's possible to take [1500120000, 10012000].[/QUOTE] Done. [CODE]1033^16254+16254^1033, 48992 1263^19898+19898^1263, 61712 1265^19732+19732^1265, 61211 1271^17368+17368^1271, 53913 1338^15377+15377^1338, 48076 1417^15754+15754^1417, 49647 1456^19909+19909^1456, 62976 1508^17691+17691^1508, 56230 1537^18832+18832^1537, 60012 1576^19021+19021^1576, 60821 1638^15437+15437^1638, 49620 1684^16495+16495^1684, 53219 1741^19546+19546^1741, 63345 1828^16589+16589^1828, 54113 1839^17156+17156^1839, 56008 1845^16636+16636^1845, 54334 1850^18879+18879^1850, 61681 1897^16710+16710^1897, 54777 1908^17605+17605^1908, 57755 1943^15222+15222^1943, 50058 [/CODE] 
And one PRP to rule them all:
15^328574+328574^15 (386434 digits) :smile: 
Reserving [40001330000, 1117]

Why not ...20]?

Because it is [I]more[/I] work? ;)
Maybe later. (19 and 20 are particularly heavy and 20^330000 >> 17^330000) Someone can relatively easily do the y=18. Free idea! Anyone? 
I am running Y=18, should make it to 300k by the end of the month unless I've screwed up my calculations somewhere.

[40001330000, 1117] is done. Three PRPs:
11^255426+255426^11 12^47489+47489^12 (previously known) 15^328574+328574^15 
Reserving [330001400000, 1117]

[QUOTE=rogue;373401]I haven't touched MultiSieve in years. It's good to know that some people still have use for it. After looking at the code (talk about a blast from the past), I think it would be easy to convert this sieve to OpenCL since it doesn't use a discrete log. An OpenCL version might 100x faster.[/QUOTE]
So I started to work on this and discovered it will be a little more work than I expected. That's okay because I found an optimization that will help it be even faster. My question to those who are searching, what % of candidates remain after searching a range? That might impact how I code certain parts of the program. 
For values one less than a prime, the candidate list shrinks dramatically immediately after starting. If the sieve is written similar to newpgen then at some point the list representation is changed to a more compact one. (Is it?) Anyway, if you take X=12, Y from 40001 to 400000, then after a few seconds of running the number of candidates shrinks from 360000 to ~2,200, then under 2000 and then goes at a not such dramatic rate.
(You would definitely want to pack this list to only multiples of the prime X+1, and probably even tighter based on some additional modular restrictions.) For values not one less than a prime, the candidate list is 34 times larger. 
[QUOTE=Batalov;373674]For values one less than a prime, the candidate list shrinks dramatically immediately after starting. If the sieve is written similar to newpgen then at some point the list representation is changed to a more compact one. (Is it?) Anyway, if you take X=12, Y from 40001 to 400000, then after a few seconds of running the number of candidates shrinks from 360000 to ~2,200, then under 2000 and then goes at a not such dramatic rate.
(You would definitely want to pack this list to only multiples of the prime X+1, and probably even tighter based on some additional modular restrictions.) For values not one less than a prime, the candidate list is 34 times larger.[/QUOTE] When both x and y are even, it is obvious that x^y+y^x is even, so you are really starting with 180,000 candidates. That creates some challenges. In the current code it starts as a bitmap, but is then changed to a vector when it determines that a vector would take less memory. With OpenCL I cannot use a vector, although I can use an array. In the new version I'm thinking about eliminating the bitmap and vector completely and forcing the user to bite off only as much as they have memory available (i.e. storing in an array). I can't imagine someone reserving a range with a billion candidates for example. The largest reservation in the past didn't even have that many candidates in it. Of note, I think that [URL="http://xyyxf.at.tut.by/primes.html#ranges"]this page[/URL] should be split so that reservations are on one page and primes/PRPs on another. The reservations should list the ymin and ymax for each reservation. The primes/PRPs should have a "when found" in addition to "when proven", but that is just an opinion. I also have the opinion that x and y should be swapped in those tables for clarification. The reason is because of how MultiSieve (and the pending xyyxsieve) work. In these programs x is always less than y, but on this webpage, it has y always less than x. I also see that the page was updated last week, but it doesn't have any reservations that have been added to this thread. 
[QUOTE=Batalov;373674]For values one less than a prime, the candidate list shrinks dramatically immediately after starting.[/QUOTE]
[B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p1, x^y+y^x is composite for all y>1 coprime with p. [B]Proof.[/B] x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x [TEX]\eq[/TEX] 1 (mod p) (little Fermat Thm.) and x^y [TEX]\eq[/TEX] p1 (mod p), so x^y+y^x has a factor p. [TEX]\qed[/TEX] Because of that, for x=12, the sieve should only consider 1/26th of the initial values, for x=18, 1/36th; for x=1600, 1/3202th, etc 
Done with [330001400000, 1117], no primes.
Reserving [400001500000, 1117]  one less step in the stepwise function, as you asked, Andrey! 
[QUOTE=Batalov;373704][B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p1, x^y+y^x is composite for all y>1 coprime with p.
[B]Proof.[/B] x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x [TEX]\eq[/TEX] 1 (mod p) (little Fermat Thm.) and x^y [TEX]\eq[/TEX] p1 (mod p), so x^y+y^x has a factor p. [TEX]\qed[/TEX] Because of that, for x=12, the sieve should only consider 1/26th of the initial values, for x=18, 1/36th; for x=1600, 1/3202th, etc[/QUOTE] Hadn't thought of that. It would certainly reduce the initial memory size considerably for certain x or y 
[QUOTE=rogue;373702]I also have the opinion that x and y should be swapped in those tables for clarification.[/QUOTE]They won't be, because Paul Leyland originally stated x > y. He also insisted that PRPs should be searched in order or increasing x.
Why not to rename x and y variables in Multisieve? :) 
[QUOTE=XYYXF;373728]They won't be, because Paul Leyland originally stated x > y. He also insisted that PRPs should be searched in order or increasing x.
Why not to rename x and y variables in Multisieve? :)[/QUOTE] I have two reasons. First, I haven't touched Multisieve in years and am not interested in updating it. Second, Multisieve also supports x^yy^x and for that to be > 0, x must be less than y. 
It is a classic case of little vs. bigendians war.
But it's not new! Swift already described it: [QUOTE=Wiki]The novel further describes an intraLilliputian quarrel over the practice of breaking eggs. Traditionally, Lilliputians broke boiled eggs on the larger end; a few generations ago, an Emperor of Lilliput, the Present Emperor's greatgrandfather, had decreed that all eggs be broken on the smaller end after he cut himself breaking the egg on the larger end. The differences between BigEndians (those who broke their eggs at the larger end) and LittleEndians had given rise to "six rebellions... wherein one Emperor lost his life, and another his crown". The Lilliputian religion says an egg should be broken on the convenient end, which is now interpreted by the Lilliputians as the smaller end. The BigEndians gained favour in Blefuscu.[/QUOTE] Let's not loose sleep over it. C'est tout de même. 
[400001500000, 1117] is done, no primes. (ME~=0.2)

[QUOTE=rogue;373744]Multisieve also supports x^yy^x and for that to be > 0, x must be less than y.[/QUOTE]I've always used version 5.5 which requires x > y :)
[url]http://www.primefan.ru/stuff/soft/ms.zip[/url] 
[QUOTE=XYYXF;374917]I've always used version 5.5 which requires x > y :)
[url]http://www.primefan.ru/stuff/soft/ms.zip[/url][/QUOTE] That was before I was asked to modify MultiSieve to support x^y  y^x. 
With both MultiSieve and its replacement for x^y+/y^x, the more squarelike the search area, the more efficient the software will be. The new software will be even more efficient based upon squareness of the search area. By "squareness" I mean xmax  xmin is close to ymax  ymin. This is because the software has to calculate both x^y mod p and y^x mod p. The software gets its efficiency by computing x^miny mod p for each x and y^minx mod p for each y then multiplying to get the next term. The software won't prohibit a flat rectangle, i.e. minx = maxx or miny = maxy, but it won't be very fast.

Nevermind my previous post.
I was looking at what I was working on and realized that it couldn't easily be done in a GPU because of the memory requirements. As I turned the problem over in my head (more than a few times) I realized that my approach to the sieve was inefficient. Although more efficient than MultiSieve, there was an obvious optimization that I completely missed. The good thing is that this optimization also simplifies the code (code I haven't written yet) quite a bit. 
And due to that simplification the code is now written. Now I have the fun of testing it...

I will be glad to help you betatest.
As you can see from my interest for these (which is predating the creation of this forum) that I have a soft spot for these PRPs (as, undoubtedly, also does Selevich). The real burden of course is the PRP testing, but an improved sieve could lift maybe 1/3 of that weight  then, that's great! 
[QUOTE=rogue;375713]Nevermind my previous post.
I was looking at what I was working on and realized that it couldn't easily be done in a GPU because of the memory requirements. As I turned the problem over in my head (more than a few times) I realized that my approach to the sieve was inefficient. Although more efficient than MultiSieve, there was an obvious optimization that I completely missed. The good thing is that this optimization also simplifies the code (code I haven't written yet) quite a bit.[/QUOTE] That optimization was a fail (and I know why). So I'm focused on getting the code at least equivalent to MultiSieve and then focus on optimizations later. That being said it shouldn't be too difficult to make that happen. 
Almost ready for release. I have to do some more testing. On my laptop (which has a slow GPU), it is only about 2x as fast as MultiSieve. I would expect a desktop with a bigger GPU to be much faster.

1 Attachment(s)
Here is a 64bit beta (Windows). I have good news and bad news about this beta. First the bad. It appears that MultiSieve removes terms for which it does not have a factor. I've looked at the code and have not been able to figure out where that is occurring. This means that ranges sieved in the past should be sieved again presuming I can't track down why it is doing it, which I have little desire to do.
Now the good. The attached program is about 4x faster than MultiSieve on my laptop (for the range below), which has an NVIDIA NVS 5200M. The performance is somewhat based upon the range of y. The larger the range of y, the better the performance. Here are the runtime options: [code] E:\stuff\sieves\xyyxsieve_1.0.0\visualstudio>xyyxsievecl64 h h help Print this help v verbose Verbose output (memory usage) q quiet Quiet output (no banner or stats) p pmin=P0 Sieve start: 3 <= P0 <= p (default P0=3) P pmax=P1 Sieve end: p < P1 <= 2^62 (default P1=P0+10^9) t nthreads=N Start N threads (default N=1) l list List available platforms and devices b blocks=B Force B blocks per device f platform=F Use platform F instead of 0 d device=D Use device D instead of 0 x min_x=x Minimum x to search X max_x=X Maximum x to search y min_y=y Minimum y to search Y max_y=Y Maximum y to search s step=s steps iterated per call to GPU f factorsinrate=f Number of factors to use when computing removal rate (default 50) m minimum X Do not report factors smaller than X (default 100000) i inputfile=i PFGW file in ABC format o outputfile=o PFGW file of remaining candidates in ABC format S sign=+//b sign to sieve for [/code] Here is an command line example: xyyxsievecl64 x100 X200 y3000 Y4000 P2e6 t2 s3000 S+ b32 oxyyx.pfgw You will want to vary options t, s, and b to maximize the performance of your machine. I'll provide source later as this can be built for Linux and OS X. 
Runs great on a GTX570, but I did encounter an error as documented below:
[CODE]$ xyyxsievecl64.exe x100 X200 y3000 Y10000 P2e6 t2 s3000 S+ oxyyx.pfgw xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x Sieve started: (cmdline) 0 <= p < 2000000 with 287349 terms OpenCL Error: Out of resources in call to clEnqueueReadBuffer argument: counter[/CODE] My GPU has ~1.2GB of RAM and usually about 1GB actually available. 
Option f (platform and factorsinrate) is used twice, and doesn't seem to come through (as platform=1)
[CODE]$ ./xyyxsievecl64.exe platform=1 d0 x100 X200 y3000 Y4000 P2e6 t2 s3000 S+ b32 oxyyx.pfgw xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x List of available platforms and devices Platform 0 has no available devices. Here is a list of platforms and devices: Platform 0 is a Advanced Micro Devices, Inc. AMD Accelerated Parallel Processing, version OpenCL 1.2 AMDAPP (938.2) No devices Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.1 CUDA 6.0.1 Device 0 is a NVIDIA Corporation GeForce GTX 570 [/CODE] 
[QUOTE=wombatman;377574]Runs great on a GTX570, but I did encounter an error as documented below:
[CODE]$ xyyxsievecl64.exe x100 X200 y3000 Y10000 P2e6 t2 s3000 S+ oxyyx.pfgw xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x Sieve started: (cmdline) 0 <= p < 2000000 with 287349 terms OpenCL Error: Out of resources in call to clEnqueueReadBuffer argument: counter[/CODE] My GPU has ~1.2GB of RAM and usually about 1GB actually available.[/QUOTE] I have seen that as well. I haven't figured it out yet. The program doesn't use that much global GPU memory so I suspect it is a problem with local GPU memory. I have a table of powers for each kernel. I'll reduce the size of that table as it has too many zeros in it. Hopefully that will help. One other issue is that the number of factors returned might be causing problems. It could be overflowing in the GPU. I'm not certain how to avoid that without losing useful information. As for two "f" options, I modified factorsinrate to use F. If anyone can provide some speed comparisons with MultiSieve that would be nice. I'm also working on a change to pfgw so that the factors output from sieving programs can be easily verified. I though I had done something like that already, but maybe I never released that code. 
The "Out of resources" seems to have been caused by having too many small factors. I'll do two things to address that. First, I'll increase the buffer size so that more factors can be collected. (I've also added a check so the program can tell you if you missed factors due to too many being found.) Second, I've added a "small primes" check to eliminate all terms that are factored by p < 100 before I start the GPU sieve. That can eliminate 75% of the terms up front.

Excellent!

1 Attachment(s)
[QUOTE=wombatman;377594]Excellent![/QUOTE]
By "Excellent!", do you mean this: 
1 Attachment(s)
[QUOTE=wombatman;377594]Excellent![/QUOTE]
or this? 
Why not both? :tu:

1 Attachment(s)
Attached is the latest code. Here is what the output looks like now. This is a rather extreme range to do. It still fails if the range gets larger. I know why, but fixing is a bigger challenge. It is probably better to take smaller ranges and paste together one file and restart from there, although I haven't test the ability to restart the sieve from the output file.
[code] xyyxsievecl64.exe x2 X2500 y3 Y7500 P1e6 t2 s2000 S+ oxyyx.pfgw xyyxsievecl v1.0.1, a GPU program to find factors numbers of the form x^y+y^x Quick elimination of terms info (in order of check): 7807501 because the term is even 1478788 because x and y have a common divisor 4472597 because the term is divisible by a prime < 100 Sieve started: (cmdline) 0 <= p < 1000000 with 1857365 terms Thread 2 has completed 1818380 of 1862363 iterations CTRLC accepted. Please wait for threads to completed.s/factor, 0.15 CPU cores, 25.6% done. ETA 07 Jul 15:53 Thread 2 has completed 383059 of 390048 iterations Sieve interrupted: 3 <= p < 1000000 26624 primes tested Clock time: 539.27 seconds at at 49 p/sec. Factors found: 1472315 Processor time: 92.09 sec. (8.53 init + 83.55 sieve). Seconds spent in CPU and GPU: 65.70 (cpu), 1044.80 (gpu) Percent of time spent in CPU vs. GPU: 5.92 (cpu), 94.08 (gpu) CPU/GPU utilization: 0.17 (cores), 1.00 (devices) Percent of GPU time waiting for GPU: 46.87 Started with 1857365 terms and sieved to 281719. 385050 remaining terms written to xyyx.pfgw [/code] 
I think I just found another "Out of resources" trigger. Working on it.

I fixed that one, but I still have a problem elsewhere. It is only an issue when trying to do obscenely large search spaces. I tried to implement different logic to collect factors, but my video card does not support the OpenCL functcion atom_min.

No problem. Like you said, smaller ranges work fine. I just wanted to point it out in case it was a larger issue than that. Very impressive work!

Thanks. This was a very difficult program to optimize. If the range of x is large you think of optimizing in one direction. If the range of y is large, then you think of optimizing in a different direction. If both are large, then you think of a way to get the best of both worlds. Unfortunately memory and latency quickly get in the way of most potential optimizations.
Due to the bug in MultiSieve, I'm going to sieve x^y+y^x for x and y < 10000. I will also update PRPNet to support an x^y+y^x search. I don't know if I'll be able to run every term (as there will probably be close to a million after sieving), but since all of them are small it might be doable. 
The platform=1 option is still ignored.
(and additionally, the existence of f and F options is denied by the program) [CODE]$ ./xyyxsievecl64.exe platform=1 x2 X2500 y7000 Y7500 P1e6 t1 s2000 S+ oxyyx.pfgw f1 F1 xyyxsievecl v1.0.1, a GPU program to find factors numbers of the form x^y+y^x Quick elimination of terms info (in order of check): 626000 because the term is even 118610 because x and y have a common divisor 357496 because the term is divisible by a prime < 100 List of available platforms and devices C:\Users\Serge\Desktop\XYYXsieve\xyyxsievecl64.exe: invalid option  F C:\Users\Serge\Desktop\XYYXsieve\xyyxsievecl64.exe: invalid option  1 [U]Platform 0 has no available devices.[/U] Here is a list of platforms and devices: Platform 0 is a Advanced Micro Devices, Inc. AMD Accelerated Parallel Processing, version OpenCL 1.2 AMDAPP (938.2) No devices Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.1 CUDA 6.0.1 Device 0 is a NVIDIA Corporation GeForce GTX 570[/CODE]Says: "[U]Platform 0 has no available devices[/U]", does not switch to platform 1 (even though instructed) and quits. Also, minor: there is no line break after "Here is a list of platforms and devices:" message. 
1 Attachment(s)
I didn't change the version number, but this should be 1.0.2.
I finally tracked down and fixed the main "Out of resources" issue. I'm referring to the one that impacts large search ranges. I wasn't reinitializing a variable in a loop. I fixed some issues with continuing from a previous output file. 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). 
I spoke too soon on the "Out of resources" issue. I thought I had nailed it, but I just one with the latest build. :censored:

[QUOTE=rogue;377570]It appears that MultiSieve removes terms for which it does not have a factor. [/QUOTE]
Just curious if this was only for xy+yx? Was it by any chance a problem for GC/GW sieves? 
[QUOTE=Batalov;377684]Just curious if this was only for xy+yx?
Was it by any chance a problem for GC/GW sieves?[/QUOTE] I don't understand your question. This program is specific for x^y+/y^x. MultiSieve is more generic. Almost every component of MultiSieve is now done much faster by other software. For example, gcwsieve is the preferred siever for Generalized Cullens and Generalized Woodalls. n*b^n+/1 uses a discrete log. x^y+/y^x does not use a discrete log. 
[QUOTE=rogue;377570]It appears that MultiSieve removes terms for which it does not have a factor. I've looked at the code and have not been able to figure out where that is occurring. This means that ranges sieved in the past should be sieved again presuming I can't track down why it is doing it, which I have little desire to do.[/QUOTE]
My question was about good old MultiSieve (because you wrote about MultiSieve's behavior). I quoted specifically the statement for which I had a followup question. gcwsieve is (of course) faster, but some legacy GC/GW projects may have been done with MultiSieve (some bases were done more than ten years ago). But if underreporting behavior was limited to the xyyx branch of MultiSieve only, then there shouldn't be any problem. 
[QUOTE=Batalov;377715]My question was about good old MultiSieve (because you wrote about MultiSieve's behavior). I quoted specifically the statement for which I had a followup question.
gcwsieve is (of course) faster, but some legacy GC/GW projects may have been done with MultiSieve (some bases were done more than ten years ago). But if underreporting behavior was limited to the xyyx branch of MultiSieve only, then there shouldn't be any problem.[/QUOTE] Yes, they use completely different logic. They do share some lower level code, but that code is not where the bug is. If it were, then it would have manifested itself when comparing MultiSieve output to gcwsieve output. 
Right!
I think multisieve ("start new sieve" option) is still faster than the setup accessory sieve gcwsieve1.3.5smallp.zip (or Pari ad hoc) ... but then (after p>N) one should switch to gcwsieve. 
The interval 20,001<=x<=40,000, 201<=y<=400 is reserved by Norbert Schneider.

Please ensure that he is not using MultiSieve due to the undiagnosed bug described earlier in this thread.
As I stated above I am sieving all y for all x < 10000 (using your nomenclature) and intend to retest to determine if any PRPs were missed. 
I just checked in changes for PRPNet into sourceforge. It now supports x^y+y^x and x^yy^x searches.

1 Attachment(s)
Here is v1.0.3. I fixed a calculation error in the stats that I inadvertently added in the previous build. I also made the following changes:
1) Delete the .ckpt file when done. 2) Write to the output file whenever the .ckpt file is written. 3) Apply factors from xyyxsieve.log to the input file before processing it. These were designed to make it safer to stop and restart without losing factors. 
I tested the program with command line:
xyyxsievecl64.exe v platform=1 x4000 X8020 y8001 Y8020 P100000 t8 s2000 S+ oxyyx_8020p.out f1 F1 When i use S+ then only the x^y+y^x numbers were sieved, when S then x^y+y^x and x^yy^x numbers were sieved, when Sb then error: Fatal Error: sign must be specified. In the help file is: S sign=+//b sign to sieve for I would like to use xyyxsievecl64.exe for only x^yy^x numbers sieve. 
My doublecheck for all x/y has yielded this:
1467^4076+4076^1467 is 3PRP! The range containing this PRP was searched prior to the creation of MultiSieve. I'm still doublechecking the range where both x and y are <= 10000. I'm about 50% complete. 
1 Attachment(s)
[QUOTE=NorbSchneider;377975]I tested the program with command line:
xyyxsievecl64.exe v platform=1 x4000 X8020 y8001 Y8020 P100000 t8 s2000 S+ oxyyx_8020p.out f1 F1 When i use S+ then only the x^y+y^x numbers were sieved, when S then x^y+y^x and x^yy^x numbers were sieved, when Sb then error: Fatal Error: sign must be specified. In the help file is: S sign=+//b sign to sieve for I would like to use xyyxsievecl64.exe for only x^yy^x numbers sieve.[/QUOTE] Sorry that I missed your post. It is fixed in the attached. BTW you can use scientific notation for most parameters. In other words you can use P1e5 instead of P100000. You're probably just testing, but I recommend using a larger range for y due to optimizations in the code. You might also want to increase s and decrease t to improve performance, but I'll leave that for you to figure out what works best on your machine. 
[QUOTE=rogue;378542]Sorry that I missed your post. It is fixed in the attached. BTW you can use scientific notation for most parameters. In other words you can use P1e5 instead of P100000.
[/QUOTE] Thank You! [SIZE=2]It works perfect. I can now sieve only XY+, only XY PRPs and the two simultaneously.[/SIZE] 
[QUOTE=rogue;378541]My doublecheck for all x/y has yielded this:
1467^4076+4076^1467 is 3PRP! The range containing this PRP was searched prior to the creation of MultiSieve. I'm still doublechecking the range where both x and y are <= 10000. I'm about 50% complete.[/QUOTE] I completed a doublecheck of the range. That was the only missing PRP. I'm continuing to doublecheck for x and y <= 12500. Unfortunately I didn't sieve as deeply as I would have liked because I took a Windows patch and now none of my OpenCL applications works on it. I have other computers, but most have a slower GPU. The one with the fastest GPU (a Mac) broke earlier this year when I installed Mavericks. I don't know what is going on with that, but I suspect that I need to reinstall the OS to fix the problem and since it is my main computer I don't want to take it down for an extended period of time to fix the problem. Eventually I will or I'll talk my wife into an upgrade (of the computer, not her :grin:). 
Here are two more PRPS that were missed. These were probably missed due to the bug in MultiSieve.
1490^11487+11487^1490 2239^12462+12462^2239 I've finished the double check where y <= 2500 and x <= 12500. I have a ways to go before finishing the rest of y <= 12500. 
Intriguingly, the second one is in factordb since July 11, 2014
P.S. EDIT: And in prptop (Norbert Schneider, 07/2014) 
[QUOTE=Batalov;379175]Intriguingly, the second one is in factordb since July 11, 2014
P.S. EDIT: And in prptop (Norbert Schneider, 07/2014)[/QUOTE] I wonder why they are missing on xyyxf's website. 
I'm Norbert Schneider.
On July 26, 2014 have I finished my search in the interval 12,051<=x<=12,500, 2001<=y<=x1. My last new PRPs have i sent to Andrey Kulsha, but he has so far the website not updated. The last PRPs: 6330^12421+12421^6330, 47218 digits, 4569^12448+12448^4569, 45558 digits, 8602^12451+12451^8602, 48990 digits, 2239^12462+12462^2239, 41749 digits. 
[QUOTE=NorbSchneider;379199]but he has so far the website not updated.[/QUOTE]I'm waiting for two C168 GNFS tasks, just a few days :)

I search now in the interval
20,001<=x<=40,000, 201<=y<=400. I reached x=21,000 and found two new PRPs: 283^20956+20956^283, 51380 digits, 359^20992+20992^359, 53637 digits. 
Two more PRPs:
2869^11736+11736^2869 3834^11473+11473^3834 Doublechecking is now complete for y <= 5000 and x <= 12500 and 10000 < y <= 125000 and x <= 12500. I'm still working on 5000 < y <= 10000 and x <= 12500. 
[QUOTE=rogue;379608]Two more PRPs:
2869^11736+11736^2869 3834^11473+11473^3834 Doublechecking is now complete for y <= 5000 and x <= 12500 and 10000 < y <= 125000 and x <= 12500. I'm still working on 5000 < y <= 10000 and x <= 12500.[/QUOTE] Verified list for y <= 7000 and x <= 12500. I'm going on vacation for 17 days starting tomorrow. This will complete while I'm gone so expect an update when I return. 
I reached x=22,000 and found one new PRP:
387^21694+21694^387, 56138 digits. 
The page is finally updated: [url]http://xyyxf.at.tut.by/primes.html#0[/url]
Please check if it's correct. 
The doublecheck has been completed for all x and y <= 12500. Nothing new to report.

I reached x=24,000 and found one new PRP:
247^23412+23412^247, 56018 digits. 
I reached x=26,000 and found one new PRP:
291^25742+25742^291, 63426 digits. 
I reached x=27,000 and found one new PRP:
267^26336+26336^267, 63905 digits. 
I reached x=30,000 and found one new PRP:
257^29356+29356^257, 70746 digits. 
reserving x=2501=> 3000 and y=12501=>15000
already found one 2696^14313+14313^2696 is a 3PRP (49104 digits) 
I reached x=31,000 and found two new PRPs:
300^30247+30247^300, 74926 digits, 241^30280+30280^241, 72128 digits. 
range x=2500>3000 and y=12500>15000 done, 6 primes found
2696^14313+14313^2696 (already reported earlier) 2844^13855+13855^2844 2858^14763+14763^2858 2880^12617+12617^2880 2950^13563+13563^2950 2975^12664+12664^2975 Edit : those are PRP, not prime. 
[QUOTE=firejuggler;387631]range x=2500>3000 and y=12500>15000 done, 6 primes found
2696^14313+14313^2696 (already reported earlier) 2844^13855+13855^2844 2858^14763+14763^2858 2880^12617+12617^2880 2950^13563+13563^2950 2975^12664+12664^2975[/QUOTE] PRPs only? 
yes, my bad, PRP only.

Of course. None of us has access to CIDE, and even with CIDE the current record is 30,008 digit size.

[QUOTE=firejuggler;387631]range x=2500>3000 and y=12500>15000 done, 6 primes found [/QUOTE]Thanks a lot :)
Now it would be nice to fill the gap 2000 < x <= 2500 for 12500 < y <= 15000 :) 
I was pretty sure It was already reserved. If no one volonteer before I come back from my trip ( mid december) ten i'll do it.

[QUOTE=firejuggler;387667]I was pretty sure It was already reserved. If no one volonteer before I come back from my trip ( mid december) ten i'll do it.[/QUOTE]Thanks a lot. BTW, could you please specify your name to put it there?
[url]http://xyyxf.at.tut.by/primes.html#0[/url] 
[QUOTE=fivemack;373604]I am running Y=18, should make it to 300k by the end of the month unless I've screwed up my calculations somewhere.[/QUOTE]Meanwhile I got y=18 for 300k < x < 500k:
[url]http://www.primefan.ru/stuff/primes/xyyx/18.txt[/url] 
All times are UTC. The time now is 19:56. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.