View Single Post
Old 2020-10-29, 09:46   #104
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

3×7×13 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
Hi Seth

It would be useful, in this and your other post, #98 if you could explain your variables - so what is "m", "d", "p" "X" - generally, for deficient primorial multiples we have tended to use the convention k*p#/d , n*p#/d or A*p#/d but actually it does not matter what you use as long as it is explained. It is also helpful to provide a small worked example where this helps understanding.

Which language are you developing the sieve in? On this group we have tended to use perl, because of dana's work providing Perl solutions for sieves, surround_primes and prev_prime and next_prime. or c++ where c++ coded programs have been made executables.

But we are all interested in something that speeds up a sieve 10000 times :) Your results pickup is impressive.
Happy to elaborate.

I wrote the sieve and related tools in c++, my first plan was to try and include it in dana's library but it's a little more special purpose (hopefully I can share later this week) and requires many non-generic functions (e.g. file writing stuff, database management) that doesn't belong in dana's library IMO. If you're interested in testing it out (or anyone) send me a PM.

I use the form N = m * p# / d - a., with m instead of your k.

---

X refers to the offset from N. similar to a above.
sieve length = the range on each side of N that I sieve (for an sieve interval of 2*X+1).

Looking at a smaller example

Code:
d optimizer for P = 101# | large prime=79 | sl=505 (5.0 merit)
Optimizing | d = 2# | 40 remaining,   322 avg gap | SL insufficient 1.871% of time
Optimizing | d = 3# | 39 remaining,   192 avg gap | SL insufficient 1.964% of time
Optimizing | d = 5# | 47 remaining,   146 avg gap | SL insufficient 0.793% of time
prob_prime_coprime = change that a number of this magnitude is prime assuming no factors less than 101
= 1 / log(101#) / ((1-1/2) * (1-1/3) * (1-1/5) ...) ~= 0.094680

for d = 2# = 2, only coprime modulo is [1] so we test N = 1*101#/2
If we look just at the interval 1*101#/2 + [1, 505] we find 40 coprime X (this includes removing the multiples of 2), the lower side (- [1, 505]) has a similar number. call these X_i.

Code:
1 * 101#/2 | 40 | 2 4 8 16 32 64 128 206 214 218 226 254 256 262 274 278 298 302 314 326 334 346 358 362 382 386 394 398 412 422 428 436 446 452 454 458 466 478 482 502
Code:
avg gap = sum( (1 - prob_prime)^(i-1) * prob_prime * X_i
SL insufficient = chance that next_prime > SL
                = (1 - prob_prime)^(40) = (1 - 0.094680)^40 = 0.01871
---

for d = 3# = 6, there are two coprime residuals [1, 5]

These have fewer X (so a larger chance of SL being insufficient) but a smaller average value (so a small expected next_prime).

Code:
1 * 101#/6 | 39 | 2 6 8 12 18 24 32 36 48 54 72 96 108 128 144 162 192 206 216 218 254 278 288 302 314 324 326 362 384 386 398 422 428 432 446 452 458 482 486 
5 * 101#/6 | 39 | 4 6 12 16 18 24 36 48 54 64 72 96 108 144 162 192 214 216 226 256 262 274 288 298 324 334 346 358 382 384 394 412 432 436 454 466 478 486 502
for d = 5# = 30, there are eight coprime residuals

They have an average of 47 coprime X_i, so a smaller chance of next_prime exceeding SL.

Code:
1 * 101#/30 | 46 | 4 10 12 18 24 30 40 48 54 60 64 72 90 100 108 120 144 150 160 162 180 192 214 240 250 262 270 274 288 298 300 324 334 358 360 382 384 394 400 412 432 450 454 478 480 502 
7 * 101#/30 | 48 | 4 6 10 16 18 24 30 36 40 48 54 60 64 90 96 100 108 120 144 150 160 180 214 216 226 240 250 256 270 274 288 298 300 324 334 346 358 360 384 394 400 436 450 454 466 478 480 486 
11 * 101#/30 | 48 | 2 8 12 18 20 24 30 32 48 50 54 60 72 80 90 108 120 128 144 150 162 180 192 200 218 240 254 270 278 288 300 302 314 320 324 360 362 384 398 422 428 432 450 452 458 480 482 500 
13 * 101#/30 | 50 | 4 6 10 12 16 24 30 36 40 54 60 64 72 90 96 100 120 144 150 160 162 180 192 214 216 226 240 250 256 262 270 274 300 324 334 346 360 382 384 394 400 412 432 436 450 454 466 480 486 502 
17 * 101#/30 | 45 | 6 8 18 20 24 30 36 48 50 54 60 80 90 96 108 120 128 144 150 180 200 206 216 218 240 254 270 278 288 300 314 320 324 326 360 384 386 398 428 446 450 458 480 486 500 
19 * 101#/30 | 45 | 6 10 12 16 18 30 36 40 48 60 72 90 96 100 108 120 150 160 162 180 192 216 226 240 250 256 262 270 288 298 300 346 358 360 382 400 412 432 436 450 466 478 480 486 502 
23 * 101#/30 | 46 | 2 6 12 20 24 30 32 36 50 54 60 72 80 90 96 120 144 150 162 180 192 200 206 216 240 254 270 300 302 314 320 324 326 360 362 384 386 422 432 446 450 452 480 482 486 500 
29 * 101#/30 | 50 | 2 6 8 12 18 20 30 32 36 48 50 60 72 80 90 96 108 120 128 150 162 180 192 200 206 216 218 240 270 278 288 300 302 320 326 360 362 386 398 422 428 432 446 450 452 458 480 482 486 500
Looking back at my original example in #98 (but with slightly newer output)
The highest chance of having a next_prime gap > 9070 is with d = 5#.

Code:
d optimizer for P = 907# | SL=9070 (10.0 merit)
Optimizing | d =     1 *  1# | 973 remaining,  2809 avg gap | SL insufficient 0.000% of time
Optimizing | d =     1 *  2# | 688 remaining,  4856 avg gap | SL insufficient 0.006% of time
Optimizing | d =     1 *  3# | 473 remaining,  4535 avg gap | SL insufficient 0.123% of time
Optimizing | d =     1 *  5# | 423 remaining,  3541 avg gap | SL insufficient 0.245% of time
Optimizing | d =     1 *  7# | 432 remaining,  2770 avg gap | SL insufficient 0.214% of time
Optimizing | d =     1 * 11# | 458 remaining,  2328 avg gap | SL insufficient 0.144% of time
with P=2503, it's maximized with d=7#
Note that this maximization depends on SL too but that relationship is larger to explain.

Code:
d optimizer for P = 2503# | SL=25030 (10.0 merit)
Optimizing | d =     1 *  1# | 2396 remaining,  7864 avg gap | SL insufficient 0.000% of time
Optimizing | d =     1 *  2# | 1662 remaining, 14483 avg gap | SL insufficient 0.007% of time
Optimizing | d =     1 *  3# | 1092 remaining, 15502 avg gap | SL insufficient 0.189% of time
Optimizing | d =     1 *  5# | 918 remaining, 13562 avg gap | SL insufficient 0.512% of time
Optimizing | d =     1 *  7# | 891 remaining, 11227 avg gap | SL insufficient 0.595% of time
Optimizing | d =     1 * 11# | 923 remaining,  9492 avg gap | SL insufficient 0.491% of time
SethTro is offline   Reply With Quote