## Other

drummers-lowrise

Message boards : Extended Sierpinski Problem : k = 202705

Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 411,020,878
RAC: 19,234

Message 152447 - Posted: 2 Dec 2021 | 13:20:54 UTC

Not yet validated:

202705 * 2^21320516

With more than 6M digits it'd be the 13th largest prime and it'll decrease the number of k's left to 8.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Eudy Silva

Joined: 26 Aug 17
Posts: 1957
ID: 918937
Credit: 558,313,219
RAC: 155,855

Message 152448 - Posted: 2 Dec 2021 | 13:30:52 UTC - in response to Message 152447.

Not yet validated:

202705 * 2^21320516

With more than 6M digits it'd be the 13th largest prime and it'll decrease the number of k's left to 8.

Awesome !
Congrats to Pavel Atnashev !
____________

"Accidit in puncto, quod non contingit in anno."
Something that does not occur in a year may, perchance, happen in a moment.

Rafael
Volunteer tester

Joined: 22 Oct 14
Posts: 909
ID: 370496
Credit: 503,208,312
RAC: 137,936

Message 152454 - Posted: 2 Dec 2021 | 16:40:43 UTC

And I just switched to ESP 2 days ago!

Dayum, should have done that last week....

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 207
ID: 1108183
Credit: 12,617,604
RAC: 8,196

Message 152455 - Posted: 2 Dec 2021 | 16:59:58 UTC

This k had the highest weight of all remaining ESP k's, which means eliminating it speeds up the project the most in the short term (it accounted for about 27% of recent tasks, so that's 27% fewer tasks to run), but the least in the long run (most likely the last k will survive until n is in the trillions or so, and there was never much risk that 202705 would take that long).

Michael Millerick
Volunteer tester

Joined: 4 Feb 09
Posts: 891
ID: 35074
Credit: 696,605,683
RAC: 961,766

Message 152457 - Posted: 2 Dec 2021 | 17:57:12 UTC - in response to Message 152454.

And I just switched to ESP 2 days ago!

The opposite tends to happen to me, I have switched away from the project just a few weeks before this current prime and the previous prime were found.

This k had the highest weight of all remaining ESP k's, which means eliminating it speeds up the project the most in the short term (it accounted for about 27% of recent tasks, so that's 27% fewer tasks to run), but the least in the long run (most likely the last k will survive until n is in the trillions or so, and there was never much risk that 202705 would take that long).

It may be true that we will not finish the conjecture projects in our lifetimes, but it will still be very satisfying to see the size of the candidates advance faster.
____________

Eudy Silva

Joined: 26 Aug 17
Posts: 1957
ID: 918937
Credit: 558,313,219
RAC: 155,855

Message 152458 - Posted: 2 Dec 2021 | 19:34:17 UTC - in response to Message 152457.

And I just switched to ESP 2 days ago!

The opposite tends to happen to me, I have switched away from the project just a few weeks before this current prime and the previous prime were found.

One way to avoid such annoyance is to just do sieving, ha !
____________

"Accidit in puncto, quod non contingit in anno."
Something that does not occur in a year may, perchance, happen in a moment.

Dave

Joined: 13 Feb 12
Posts: 3118
ID: 130544
Credit: 2,187,828,658
RAC: 203,762

Message 152459 - Posted: 2 Dec 2021 | 20:30:42 UTC - in response to Message 152458.

One way to avoid such annoyance is to just do sieving, ha !

AP & sieving - the best strategy for TdP.

Eudy Silva

Joined: 26 Aug 17
Posts: 1957
ID: 918937
Credit: 558,313,219
RAC: 155,855

Message 152464 - Posted: 2 Dec 2021 | 22:00:34 UTC - in response to Message 152459.

One way to avoid such annoyance is to just do sieving, ha !

AP & sieving - the best strategy for TdP.

Sieving would be for a TdF, Tour de Factors :)
____________

"Accidit in puncto, quod non contingit in anno."
Something that does not occur in a year may, perchance, happen in a moment.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 411,020,878
RAC: 19,234

Message 152473 - Posted: 3 Dec 2021 | 15:49:26 UTC - in response to Message 152455.

This k had the highest weight of all remaining ESP k's, which means eliminating it speeds up the project the most in the short term (it accounted for about 27% of recent tasks, so that's 27% fewer tasks to run), but the least in the long run (most likely the last k will survive until n is in the trillions or so, and there was never much risk that 202705 would take that long).
Trillions, really? So without a big jump in computer hardware we'd likely never solve the Sierpinski problem in the forseeable future or even for centuries?

Is it possible to derive that number from the weight?

In that regard, can it happen that an exponent that has produced primes up to exponent x, will become a Sierpinski number for n > x ? I feel like it could, if suitable factors come up that match the gaps and create a covering set, but I'm not sure.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 747
ID: 164101
Credit: 305,277,717
RAC: 1,638

Message 152475 - Posted: 3 Dec 2021 | 16:30:39 UTC - in response to Message 152473.

Trillions, really? So without a big jump in computer hardware we'd likely never solve the Sierpinski problem in the forseeable future or even for centuries?
Is it possible to derive that number from the weight?

Yes, see weight.pdf.
The Riesel problem, ESP, PSP and SR5 can't be solved with computers if no new algorithm that drastically reduces the complexity of primality testing is found.
For the Sierpinski problem, the expected value for nmax is about 1013, but we can be "lucky" and find that nmax ~ 1012. But nmax < 1010 is unlikely.
On the bright side, if you find a SOB prime then it may be the largest known prime of the Sierpinski list for centuries!

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 207
ID: 1108183
Credit: 12,617,604
RAC: 8,196

Message 152481 - Posted: 4 Dec 2021 | 7:10:33 UTC - in response to Message 152473.

In that regard, can it happen that an exponent that has produced primes up to exponent x, will become a Sierpinski number for n > x ? I feel like it could, if suitable factors come up that match the gaps and create a covering set, but I'm not sure.

That's a very difficult question, which I've talked to JeppeSN about on Discord before. It almost certainly happens with k=1, if you count that: 1 * 2^n + 1 is prime when n = (0,) 1, 2, 4, 8, 16, and probably no other n's. If k>1, then it couldn't happen for the "usual reasons" (i.e. covering sets + algebraic factors) unless one of the primes in the covering set happens to be in the sequence k * 2^n + 1. This would be surprising, because usually the primes in a covering set are very small compared to k. But there are lots of numbers out there[citation needed], so maybe a miracle is possible.

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 207
ID: 1108183
Credit: 12,617,604
RAC: 8,196

Message 152483 - Posted: 4 Dec 2021 | 7:39:38 UTC - in response to Message 152473.

Trillions, really? So without a big jump in computer hardware we'd likely never solve the Sierpinski problem in the forseeable future or even for centuries?

Is it possible to derive that number from the weight?

Yes, given weight w, the number of primes between n=a and n=b can be modeled as a Poisson random variable with expectation w * log_2(b/a), so the probability of finding at least one prime in this range is approximately 1 - e^(-w * log_2(b/a)).

Based on this (and some rough estimates of the weights of the remaining k's), we have a 10% (resp. 50%, 90%) chance of finishing SoB when n is 227 (resp. 297000, 2.73 * 10^12) times its current value. For ESP, the corresponding numbers are 603, 168000, and 6.3 * 10^9. (I give the ratios instead of the actual values of n because the ratios will stay constant as the search continues, until we find another prime.)

Curiously, it appears that SoB is more likely to get lucky and finish "soon", whereas ESP will finish sooner in the median and unlucky cases. I would attribute this to SoB having a few very low-weight k's (which could get lucky or take centuries), while ESP has a larger number of k's but none with quite as low weight.

PS I'm sure Yves has more accurate values of the weights than I do, so if he has up-to-date predictions of this sort then you should trust him over me.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 411,020,878
RAC: 19,234

Message 152508 - Posted: 6 Dec 2021 | 8:50:25 UTC - in response to Message 152481.

That's a very difficult question, which I've talked to JeppeSN about on Discord before.
If you couldn't answer it, then I very likely can't, but here are some thoughts.

If there is a k for which only every m'th exponent n can produce a prime because every other value is covered by the covering set, then a single factor p that would exactly "plug that hole" would have to have multiplicative order m and also turn up for an exponent n that is in one of the holes in the covering set (pardon the nomenclature), correct? But the first time that p occurs in the series will be at n < p. So the "gap" between the "holes" in the covering set will have to be larger than the largest n for which the gap still occurs to be able to be plugged by a single new factor. And of course, if the holes come in irregular distances like every r'th, every s'th, every r'th, ... then certainly more than one new factor is required.

The question is, will new factors always be able to periodically fill a specific fraction of the holes? I guess the possibility is always there, so it might turn into a Sierpinski number.

I hope it's clear what I meant.

Yes, see weight.pdf.
Thanks, very interesting reading, I'll try and make my way through it.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

dukebg
Volunteer tester

Joined: 21 Nov 17
Posts: 242
ID: 950482
Credit: 23,670,125
RAC: 0

Message 152533 - Posted: 7 Dec 2021 | 11:38:01 UTC - in response to Message 152508.

The question is, will new factors always be able to periodically fill a specific fraction of the holes? I guess the possibility is always there, so it might turn into a Sierpinski number.

I hope it's clear what I meant.

That's actually an easy question to answer.

If a number k*b^n+1 has a prime factor q then rearranging you get b^n = -1*inverse(k) (mod q). The right side is a constant. Obviously, this will be true for any n(m) = n + G * m, where m is any integer and G is the group order of b – i.e. the period of the sequence b(n) = b^n (mod q).

In other words, every factor that you find for a number of form k*b^n+1 is always a factor for an infinite amount of these numbers – their series of n's form an arithmetic progression.

That's basically how you construct the covering sets for these numbers. You get a set of primes whose group orders line up nicely inside a least common multiple and you adjust the K to have each of them cover different remainders.

And even if you find a "k*b^n+1" number that is a prime itself – it itself is a factor for a series of further n's. The difference in that series would be the group order of b in (mod k*b^n+1)

Back to the question, the problem is whether or not all these covering arithmetic progressions will cover everything. Well, as prime grows arbitrary bigger, the group orders grow arbitrary bigger too. And if you aim to cover all remainders with some target LCM that I mentioned above, there's only a finite amount of them – it's easy to show all of them have to be factors of b^LCM - 1. So you constantly have to move into bigger and bigger territories. And all primes that you find have to be included in the covering set and boost the "target LCM" to a ridiculous degree

So yeah, maybe with a 6-million digit prime there would be a covering set for all the larger numbers. But it will likely include a 6-million digit number of entries in the covering set.

JeppeSN

Joined: 5 Apr 14
Posts: 1756
ID: 306875
Credit: 47,015,245
RAC: 14,000

Message 152547 - Posted: 7 Dec 2021 | 22:37:12 UTC

By the way, the prime linked in the top post in this thread has been validated now. Pavel Atnashev is now fourth by prime score. /JeppeSN

Scott Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2343
ID: 1178
Credit: 17,190,865,230
RAC: 9,778,893

Message 152612 - Posted: 12 Dec 2021 | 22:05:06 UTC - in response to Message 152547.

By the way, the prime linked in the top post in this thread has been validated now. Pavel Atnashev is now fourth by prime score. /JeppeSN

Well, at least for a few days. ;)

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 2149
ID: 126266
Credit: 7,064,997,681
RAC: 739,188

Message 152613 - Posted: 12 Dec 2021 | 23:34:31 UTC

🤔 🥺 something in the pipe Scott? 🤞🙏
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26

tng

Joined: 29 Aug 10
Posts: 458
ID: 66603
Credit: 43,199,773,225
RAC: 23,017,747

Message 152614 - Posted: 13 Dec 2021 | 0:29:53 UTC - in response to Message 152613.

Check the standings.
____________

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 2149
ID: 126266
Credit: 7,064,997,681
RAC: 739,188

Message 152622 - Posted: 13 Dec 2021 | 8:55:24 UTC

I didn't realise it was that close.
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26

JeppeSN

Joined: 5 Apr 14
Posts: 1756
ID: 306875
Credit: 47,015,245
RAC: 14,000

Message 152639 - Posted: 13 Dec 2021 | 22:00:14 UTC

Seems like at the time I wrote that, one MEG prime from Scott Brown would be enough to reclaim the fourth place. He has found two of them since. /JeppeSN

Pavel Atnashev

Joined: 11 Aug 17
Posts: 57
ID: 914937
Credit: 4,071,047,158
RAC: 2,208,883

Message 152644 - Posted: 14 Dec 2021 | 6:54:21 UTC

Looks like I need another ESP.

Scott Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2343
ID: 1178
Credit: 17,190,865,230
RAC: 9,778,893

Message 152649 - Posted: 14 Dec 2021 | 12:22:28 UTC - in response to Message 152644.

Looks like I need another ESP.

I predict you'll find it just after I get into the top 3 on the list. Every time I get into the top 3, someone finds something big and pushes me back down to fourth or lower.

...Now, I just need 25 or so more MEGA to make that happen... ;)

tng

Joined: 29 Aug 10
Posts: 458
ID: 66603
Credit: 43,199,773,225
RAC: 23,017,747

Message 152654 - Posted: 14 Dec 2021 | 13:52:36 UTC - in response to Message 152644.

Looks like I need another ESP.

Uh-oh -- I need to find something.

____________

Pooh Bear 27

Joined: 10 May 09
Posts: 787
ID: 39821
Credit: 1,635,039,188
RAC: 1,612,593

Message 152658 - Posted: 14 Dec 2021 | 15:55:32 UTC

To date, I have found ONE Mega prime, back in 2012. Almost 10 years ago. I have crunched most of those years, but it often seems the same people get Mega primes a lot more often. I really don't care, but it would be nice to get a second hit sometime before the 25-Feb, which is the 10th anniversary. Technically mine was found on PSA, so it's even a little more unique than most of the finds now.
____________
My lucky numbers are 121*2^4553899-1 and 3756801695685*2^666669±1
My movie https://vimeo.com/manage/videos/502242

Anthony Ayiomamitis

Joined: 19 Mar 15
Posts: 2989
ID: 386066
Credit: 1,094,888,138
RAC: 895,752

Message 152685 - Posted: 16 Dec 2021 | 16:55:49 UTC - in response to Message 152658.

I am still after my first mega prime! :-(

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 411,020,878
RAC: 19,234

Message 152752 - Posted: 20 Dec 2021 | 15:57:09 UTC - in response to Message 152685.

Same here. It depends a lot on the projects you crunch how fast you'll succeed. Going with the conjectures obviously makes success rather unlikely, while PPS and GFN-17 Mega should provide a hit faster. If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime. A somewhat decent 10-core can maybe do 400 tests a day, so it should take 2 months.

GFN-17 is a bit more complicated due to DC, so unless you have a very fast card, going by CPU is probably the better choice.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 207
ID: 1108183
Credit: 12,617,604
RAC: 8,196

Message 152754 - Posted: 20 Dec 2021 | 17:00:18 UTC - in response to Message 152752.

If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.

1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 747
ID: 164101
Credit: 305,277,717
RAC: 1,638

Message 152756 - Posted: 20 Dec 2021 | 17:31:16 UTC - in response to Message 152754.

If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.

1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.

For GFN-17M, we have #digits ~ 1,046,000 and p_max = 250000P then #candidates/prime ~ 29000.

JeppeSN

Joined: 5 Apr 14
Posts: 1756
ID: 306875
Credit: 47,015,245
RAC: 14,000

Message 152766 - Posted: 21 Dec 2021 | 21:49:52 UTC - in response to Message 152756.

If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.

1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.

For GFN-17M, we have #digits ~ 1,046,000 and p_max = 250000P then #candidates/prime ~ 29000.

So only #(digits)/36 workunits to find a prime here; but there are two completed tasks needed per workunit. /JeppeSN

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 411,020,878
RAC: 19,234

Message 152776 - Posted: 23 Dec 2021 | 6:55:36 UTC - in response to Message 152754.

If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.

1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.
That would correspond to a sieving rate of about 1.4%?

Btw, I was looking at the stats and saw that the number of workunits per 1M range of k for Woodall numbers decreases steadily with increasing k. For example 1M < k < 2M there were 36000 workunits and for 18M < k < 19M there were only 28000. Cullen shows a similar trend, but way less pronounced.

Were the larger numbers sieved more deeply or is there another reason?
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 207
ID: 1108183
Credit: 12,617,604
RAC: 8,196

Message 152779 - Posted: 23 Dec 2021 | 17:02:35 UTC - in response to Message 152776.

If I'm not wrong and also assuming a sieving percentage of 1%, about 23000 tests are required to produce a mega prime.

1% sounds a bit optimistic to me. My rule of thumb is that the number of tasks needed to find a prime is roughly #(digits)/30.
That would correspond to a sieving rate of about 1.4%?

Yeah, only a bit optimistic. And I guess I was a bit pessimistic.
Btw, I was looking at the stats and saw that the number of workunits per 1M range of k for Woodall numbers decreases steadily with increasing k. For example 1M < k < 2M there were 36000 workunits and for 18M < k < 19M there were only 28000. Cullen shows a similar trend, but way less pronounced.

Were the larger numbers sieved more deeply or is there another reason?

This thread has gotten way off topic already. If you want to talk about CW sieve density, you should make a new thread about it (or look at this old one).

Message boards : Extended Sierpinski Problem : k = 202705