mersenneforum.org (https://www.mersenneforum.org/index.php)
-   XYYXF Project (https://www.mersenneforum.org/forumdisplay.php?f=110)
-   -   Leyland Primes (x^y+y^x primes) (https://www.mersenneforum.org/showthread.php?t=19347)

 Batalov 2014-05-16 21:30

Reserving [330001-400000, 11-17]

 rogue 2014-05-16 22:40

[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.

 Batalov 2014-05-16 22:54

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 2014-05-17 17:34

[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 3-4 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.

 Batalov 2014-05-17 18:44

[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=p-1, 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] p-1 (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

 Batalov 2014-05-17 19:02

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 2014-05-17 21:23

[QUOTE=Batalov;373704][B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p-1, 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] p-1 (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

 XYYXF 2014-05-17 22:57

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

 rogue 2014-05-18 02:42

[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^y-y^x and for that to be > 0, x must be less than y.

 Batalov 2014-05-18 03:07

It is a classic case of little- vs. big-endians war.
But it's not new! Swift already described it:
[QUOTE=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.[/QUOTE]
Let's not loose sleep over it. C'est tout de même.

 Batalov 2014-05-19 06:25

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

All times are UTC. The time now is 19:46.