20140516, 21:30  #23 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
41·229 Posts 
Reserving [330001400000, 1117]

20140516, 22:40  #24  
"Mark"
Apr 2003
Between here and the
2×43×73 Posts 
Quote:
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. 

20140516, 22:54  #25 
"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 34 times larger. 
20140517, 17:34  #26  
"Mark"
Apr 2003
Between here and the
2×43×73 Posts 
Quote:
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. 

20140517, 18:44  #27  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010010101101_{2} Posts 
Quote:
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 p1 (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 

20140517, 19:02  #28 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010010101101_{2} Posts 
Done with [330001400000, 1117], no primes.
Reserving [400001500000, 1117]  one less step in the stepwise function, as you asked, Andrey! 
20140517, 21:23  #29  
"Mark"
Apr 2003
Between here and the
1100010000110_{2} Posts 
Quote:


20140517, 22:57  #30  
Jan 2005
Minsk, Belarus
110010000_{2} Posts 
Quote:
Why not to rename x and y variables in Multisieve? :) 

20140518, 02:42  #31 
"Mark"
Apr 2003
Between here and the
2×43×73 Posts 
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.

20140518, 03:07  #32  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
41×229 Posts 
It is a classic case of little vs. bigendians war.
But it's not new! Swift already described it: Quote:


20140519, 06:25  #33 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
41×229 Posts 
[400001500000, 1117] is done, no primes. (ME~=0.2)

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Leyland Primes: ECPP proofs  Batalov  XYYXF Project  16  20190804 00:32 
Mersenne Primes p which are in a set of twin primes is finite?  carpetpool  Miscellaneous Math  3  20170810 13:47 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
On Leyland Primes  davar55  Puzzles  9  20160315 20:55 
possible primes (real primes & poss.prime products)  troels munkner  Miscellaneous Math  4  20060602 08:35 