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

[Batalov]

Reserving [330001-400000, 11-17]

[rogue]

Originally Posted by rogue

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.

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.

[Batalov]

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 3-4 times larger.

[rogue]

Originally Posted by Batalov

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 3-4 times larger.

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 this page 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.

[Batalov]

Originally Posted by Batalov

For values one less than a prime, the candidate list shrinks dramatically immediately after starting.

Lemma (the obvious) 1. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

Proof. x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x 1 (mod p) (little Fermat Thm.) and x^y p-1 (mod p), so x^y+y^x has a factor p.

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

[Batalov]

Done with [330001-400000, 11-17], no primes.

Reserving [400001-500000, 11-17] - one less step in the stepwise function, as you asked, Andrey!

[rogue]

Originally Posted by Batalov

Lemma (the obvious) 1. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

Proof. x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x 1 (mod p) (little Fermat Thm.) and x^y p-1 (mod p), so x^y+y^x has a factor p.

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

Hadn't thought of that. It would certainly reduce the initial memory size considerably for certain x or y

[XYYXF]

Originally Posted by rogue

I also have the opinion that x and y should be swapped in those tables for clarification.

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? :-)

[rogue]

Originally Posted by XYYXF

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? :-)

I have two reasons. First, I haven't touched Multisieve in years and am not interested in updating it. Second, Multisieve also supports x^y-y^x and for that to be > 0, x must be less than y.

[Batalov]

It is a classic case of little- vs. big-endians war.
But it's not new! Swift already described it:

Originally Posted by Wiki

The novel further describes an intra-Lilliputian 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 great-grandfather, 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 Big-Endians (those who broke their eggs at the larger end) and Little-Endians 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 Big-Endians gained favour in Blefuscu.

Let's not loose sleep over it. C'est tout de même.

[Batalov]

[400001-500000, 11-17] is done, no primes. (ME~=0.2)