mersenneforum.org Leyland Primes (x^y+y^x primes)
 Register FAQ Search Today's Posts Mark Forums Read

 2014-05-16, 21:30 #23 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41·229 Posts Reserving [330001-400000, 11-17]
2014-05-16, 22:40   #24
rogue

"Mark"
Apr 2003
Between here and the

2×43×73 Posts

Quote:
 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.

 2014-05-16, 22:54 #25 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41·229 Posts 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.
2014-05-17, 17:34   #26
rogue

"Mark"
Apr 2003
Between here and the

2×43×73 Posts

Quote:
 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.

2014-05-17, 18:44   #27
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101011012 Posts

Quote:
 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 $\eq$ 1 (mod p) (little Fermat Thm.) and x^y $\eq$ p-1 (mod p), so x^y+y^x has a factor p. $\qed$

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

 2014-05-17, 19:02 #28 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100101011012 Posts Done with [330001-400000, 11-17], no primes. Reserving [400001-500000, 11-17] - one less step in the stepwise function, as you asked, Andrey!
2014-05-17, 21:23   #29
rogue

"Mark"
Apr 2003
Between here and the

11000100001102 Posts

Quote:
 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 $\eq$ 1 (mod p) (little Fermat Thm.) and x^y $\eq$ p-1 (mod p), so x^y+y^x has a factor p. $\qed$ 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

2014-05-17, 22:57   #30
XYYXF

Jan 2005
Minsk, Belarus

1100100002 Posts

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

2014-05-18, 02:42   #31
rogue

"Mark"
Apr 2003
Between here and the

2×43×73 Posts

Quote:
 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.

2014-05-18, 03:07   #32
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts

It is a classic case of little- vs. big-endians war.
But it's not new! Swift already described it:
Quote:
 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.

 2014-05-19, 06:25 #33 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 41×229 Posts [400001-500000, 11-17] is done, no primes. (ME~=0.2)

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov XYYXF Project 16 2019-08-04 00:32 carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 davar55 Puzzles 9 2016-03-15 20:55 troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 22:01.

Tue Apr 13 22:01:59 UTC 2021 up 5 days, 16:42, 1 user, load averages: 2.66, 2.30, 2.08