Alternative Sieving for 10M digit prime search - Page 2

jasong · 2006-11-04, 00:24

Quote:

Originally Posted by CedricVonck

FWIW, I am doing the search from 33.2M to 100M, 3M candidates remaining.

That is a LOT of candidates!!!

ValerieVonck · 2006-11-04, 10:26

Quote:

Originally Posted by jasong

That is a LOT of candidates!!!

Yes but I am eliminating n's each 0.5 second...

Cruelty · 2006-11-08, 10:16

Quote:

Originally Posted by japelprime

For k=7, K*b^n+1, n=33219281 - 33259281 (40.000 candidates)
Sieve with NPGen up to 1.1 trillion.
there is 1996 n's remaining (candidates)

I am not very familiar with "+" test but single test on such big exponent should take you 8-10 weeks on today's high-end machine.

Quote:

Originally Posted by japelprime

For k=7, K*b^n-1, n=33219281 - 33259281 (40.000 candidates)
Sieve with NPGen up to 1.2 trillion.
there is 840 n's remaining (candidates)

Here it should be a little bit faster ~6 weeks per exponent on today's high-end machine.

Quote:

Originally Posted by japelprime

I was estimating that sieving up to 1.500 trillion will be the goal here (bit >50 if I am correct) and see what will be left?

...and I will continue sieving ….

If you plan to reach p=1.5*10^15 using NewPGen, then it will take you several years to complete. I've been playing some time ago with some k<300 and n>10^7. Daily rate was ~1.1T with a range of n=30000, and ~350 remaining candidates (Athlon64 @ 2.2GHz). I don't want to discourage any of you, but IMO the chances that you even complete those ranges is minimal, not to mention the chance of finding a prime in a given range (especially looking at the density of those primes till n<1630000)

Instead I would consider looking for Gaussian Mersenne norms. Jean Penné has already pre-sieved candidates (n<40000000) for both GM and GQ searches till 32 bits, and has made this file available to public. Using his latest LLR software you may factor (till 86bits) and test those exponents that can compete with current Mersenne Primes

japelprime · 2006-11-08, 22:09

Thanks for the advice Cruelty.

I said to jasong after his idea about doing some sieving with 10M numbers that this was to crazy ....and that is why I like it.

The reason I did k=7 (and this will probably sound silly). I will have fewer candidates left for LLR test than doing k=3, 5 and 9. And because of this it is maybe possible for the big cruncers to grab some of this remaining candidates and finish this in the future if they feel they can get lucky.

I will never finish this alone and I think the jasong´s idea was to share this with others here.... and with multisieving it is not holy insane doing this up to p=1.5*10^15 (using NewPGen ) in the nearest future.

Like my new avatar indicates I will only be able to galloping with my old PC’s through some numbers with sieving effort.

I am up to 2*10^12 and 1947 candidates remaining for +1
827 candidates remaining for -1

Maybe there should be a forum here for the crazy ones.

Cruelty · 2006-11-08, 23:13

Quote:

Originally Posted by japelprime

Maybe there should be a forum here for the crazy ones.

I wouldn't call you crazy... inspired maybe

Who knows, maybe in 50-60 years testing single 10M number will be a matter of hours, and at that time you and jasong might be considered pioneers?
Anyways, I wish you luck - you will certainly need it.

ValerieVonck · 2006-12-06, 11:30

Going to sieving on my 3M candidates and going to limit the search to 40.000 candidates.

I will try to upload the complete zipped range on my site.

Regards.
C.

japelprime · 2006-12-06, 23:02

Sieving up to 7,2*10^12 for +1: 1869 candidates remaining.
and 6*10^12 for -1 798 candidates remaining.
Still on bit 42

ValerieVonck · 2007-01-05, 08:35

Sieved 9 upto 80G - 36.000 candidates remaining

Citrix · 2007-01-27, 04:00

Quote:

Originally Posted by jasong

Awesome.

I'm going to receive some AMD parts in about a week. Sometime in the week after that they'll be running Linux. Then I'll finally be able to help with this.

I just wanted to check if there is still some interest in taking 3^16 further, possibly find a 10M digit prime.

Did some preliminary sieving stuff.
Range of n=1million to 50 Million
700,000 candidates left at p=10 billion.
Rate=4000 candidates per billion removed at p=10 billion
Speed= 3 Mp/s on a 1.6 ghz Intel celeron chip using srsieve for 3^16. (The sieve is supposed to get faster as soon as Geoff can implement the SPH algorithm)

Anyone interested in helping out etc, else I can work on n=1to 2M range. (If some one is interested in helping, we can start a coordination thread for 3^16 some where on the forum.)

Thanks

ValerieVonck · 2007-01-27, 08:35

Quote:

Originally Posted by Citrix

Anyone interested in helping out etc, else I can work on n=1to 2M range. (If some one is interested in helping, we can start a coordination thread for 3^16 some where on the forum.)

Thanks

Always interested to help out

If you give me the right instructions

VBCurtis · 2007-01-30, 17:53

In the interest of efficiency, you would be vastly better off choosing one k to test together, and sieving more than 40,000 candidates. If you're going to tackle such a long project, why not do the sieving on a large enough range to produce one expected prime?

The lower the weight of your chosen k, the less likely you are to find a prime; it would likely make sense to choose 15, the highest weight k under 31, as your target k-value. 15 produces on average 3 primes per doubling of exponent, or one per 25% increase in exponent. Sieving from 33.22M to 42M or so would produce one expected prime in the candidate pool.

The key thing here is that sieving efficiency rises with the square root of the range-- two 40k ranges is 1.4 times as much work as one 80k range. If you simply chose one k value, you could sieve a 360k range in the same time it takes you to run the three separate sieves you have set up now. Also, consider the prob of finding a prime in even a 360k range. Say you get the project done, and the 4% chance of a prime in a 360k range (of 15, let alone a lower-weight k) does not come to pass. Do you start over? Again, restarting a sieve is wasting work compared to sieving all at once from the start. Your 40k ranges of candidates have a <1% chance of containing a prime.

Note that someone, sometime, will eventually LLR your sieved range if you complete it.

As for proper sieve depth, bit depth is not important-- what is important is removing candidates faster than an LLR test would take. On current hardware, that means you'd sieve until expected sieve-removal rate was worse than every 6 weeks or so. There's a formula for determining this rate, so you could solve for proper sieve depth once you have decent amount done. The bit depth GIMPS uses is determined by this equivalence also.

You all could sieve 15 (or 7 or 9) by just reserving a p-range, and all using the same starting file, which should be done to 1T or so before distribution.

-Curtis

2006-12-06, 23:02	#18
japelprime "Erling B." Dec 2005 3×5×7 Posts	*k=7, Kb^n plusminus 1, n=33219281 - 33259281 (40.000 candidates)** Sieving up to 7,210^12 for +1: 1869 candidates remaining. and 610^12 for -1 798 candidates remaining. Still on bit 42

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Search of all even-15-digit Aliquot cycles	Drdmitry	Aliquot Sequences	25	2016-12-16 15:26
Polynomial search for 204-digit cofactor of M1009	fivemack	Factoring	45	2012-02-14 08:50
Deep Sieving 10m Digit Candidates	lavalamp	Open Projects	53	2008-12-01 03:59
Help Sieving 10 Million Digit Candidates	lavalamp	Riesel Prime Search	26	2008-05-25 08:24
idea about 10 million digit search(possibly dumb)	jasong	Math	5	2006-06-07 10:39

2006-11-08, 22:09	#15
japelprime "Erling B." Dec 2005 3·5·7 Posts	Thanks for the advice Cruelty. I said to jasong after his idea about doing some sieving with 10M numbers that this was to crazy ....and that is why I like it. The reason I did k=7 (and this will probably sound silly). I will have fewer candidates left for LLR test than doing k=3, 5 and 9. And because of this it is maybe possible for the big cruncers to grab some of this remaining candidates and finish this in the future if they feel they can get lucky. I will never finish this alone and I think the jasong´s idea was to share this with others here.... and with multisieving it is not holy insane doing this up to p=1.510^15 (using NewPGen ) in the nearest future. Like my new avatar indicates I will only be able to galloping with my old PC’s through some numbers with sieving effort. I am up to 210^12 and 1947 candidates remaining for +1 827 candidates remaining for -1 Maybe there should be a forum here for the crazy ones.

2006-12-06, 11:30	#17
ValerieVonck Mar 2004 Belgium 7×11² Posts	Going to sieving on my 3M candidates and going to limit the search to 40.000 candidates. I will try to upload the complete zipped range on my site. Regards. C.

2007-01-05, 08:35	#19
ValerieVonck Mar 2004 Belgium 34F₁₆ Posts	Sieved 9 upto 80G - 36.000 candidates remaining

2007-01-30, 17:53	#22
VBCurtis "Curtis" Feb 2005 Riverside, CA 2·2,927 Posts	In the interest of efficiency, you would be vastly better off choosing one k to test together, and sieving more than 40,000 candidates. If you're going to tackle such a long project, why not do the sieving on a large enough range to produce one expected prime? The lower the weight of your chosen k, the less likely you are to find a prime; it would likely make sense to choose 15, the highest weight k under 31, as your target k-value. 15 produces on average 3 primes per doubling of exponent, or one per 25% increase in exponent. Sieving from 33.22M to 42M or so would produce one expected prime in the candidate pool. The key thing here is that sieving efficiency rises with the square root of the range-- two 40k ranges is 1.4 times as much work as one 80k range. If you simply chose one k value, you could sieve a 360k range in the same time it takes you to run the three separate sieves you have set up now. Also, consider the prob of finding a prime in even a 360k range. Say you get the project done, and the 4% chance of a prime in a 360k range (of 15, let alone a lower-weight k) does not come to pass. Do you start over? Again, restarting a sieve is wasting work compared to sieving all at once from the start. Your 40k ranges of candidates have a <1% chance of containing a prime. Note that someone, sometime, will eventually LLR your sieved range if you complete it. As for proper sieve depth, bit depth is not important-- what is important is removing candidates faster than an LLR test would take. On current hardware, that means you'd sieve until expected sieve-removal rate was worse than every 6 weeks or so. There's a formula for determining this rate, so you could solve for proper sieve depth once you have decent amount done. The bit depth GIMPS uses is determined by this equivalence also. You all could sieve 15 (or 7 or 9) by just reserving a p-range, and all using the same starting file, which should be done to 1T or so before distribution. -Curtis