mersenneforum.org Software/instructions/questions
 Register FAQ Search Today's Posts Mark Forums Read

2010-06-23, 19:09   #67
Flatlander
I quite division it

"Chris"
Feb 2005
England

31×67 Posts

I'm making a program that calls srsieve then examines the output to give the probabilities of finding a prime by a certain n; as per my question above.

I am using the formulae from your spreadsheet and notice that there is the constant 1.781 in C10. Where does this come from and do I need more significant figures?

You recommend sieving to 1G. Will I lose accuracy by choosing 100M to get a quicker result?

Quote:
 Originally Posted by gd_barnes For the n-value, use a little less than the average of the range; let's say n=140K.
Why 'a little less'?

2010-06-24, 08:14   #68
gd_barnes

"Gary"
May 2007
Overland Park, KS

22·11·269 Posts

Quote:
 Originally Posted by Flatlander I'm making a program that calls srsieve then examines the output to give the probabilities of finding a prime by a certain n; as per my question above. I am using the formulae from your spreadsheet and notice that there is the constant 1.781 in C10. Where does this come from and do I need more significant figures? You recommend sieving to 1G. Will I lose accuracy by choosing 100M to get a quicker result? Why 'a little less'?

AXN came up with the 1.781 constant back about 3 years ago in an RPS thread. Although most are my own, I incorporated a couple of his formulas in the spreadsheet that were over my head to calculate.

Yes, you'll lose a little bit of accuracy with a lower sieve but not a lot. P=1G is pretty fast for one k. You might test the difference.

Think about your 2nd question mathematically. Hint: The chance of prime at each n-level does not drop in a linear fashion. Actually, as n approaches infinity, the % of each n-range that you should use for the "average n" (call it A) would converge on 50, i.e. the true average of the n-range. Technically, the A-value of 40 that I gave was a very rough estimate. 2 examples at the extremes demonstrate this: Let's say you were doing n=1K-1M. The true average is of course near n=500K but A would probably be close to 30, which would mean that you need to use n=300K. For n=10M-11M, A would be very near 50 (likely 45-47 somewhere), which means you would use n=10.5M. The pattern that holds is: If max n / min n divided by the average size of n (call that R) is extremely high as in the former example, than A is very low, possibly as low as 30. If R is extremely low as in the latter example, than A converges on as high as it can be: 50; that is the true average of the n-range.

Actually, I believe it is very possible that the lowest value of A might be the log of 2 base 10, which is .30103. So if max n/min n was very large and the average n was very small, then A would be near 30.103. But I would have to test that to be sure. That is only educated speculation.

I could calculate exact figures across many ranges but it would be tedious and have to be done by trial and error because I don't know enough high-level math to utilize calculus to do it. You would have to take it down to n-ranges that are 1/100th or 1/1000th of your total n-range and add them all together. I only suggest dividing up your sieve ranges into 10, 20, or 30.

What would be more accurate for an n=100K-2M range that you might need to sieve would be to use n=135K for the n=100K-200K range, n=238K for the n=200K-300K range, n=340K for the n=300K-400K range, etc. with the n-range being used gradually converging on 50% of the actual n-range being tested so that it is something like n=1.948M for n=1.9M-2M. But I have no way to know if those are completely accurate. I chose 40% or n=140K (for n=100K-200K) because that is likely to be a reasonably close average over the entire very large n-range that you'd need to sieve just to get a 60-70% chance of prime.

BTW, one final example: Max and I tested Sierp base 9 from n=360K-800K after I sieved n=360K-1M. I remembered commenting to Max, after using the exact method that I showed you to use here that we only had a 20-25% chance of prime for the entire n=360K-1M range. It likely would have needed sieving n=360K-3M to get nearly a 70% chance of prime (If there is no prime by n=1M, it would then probably need sieving n=1M-7M at least!). And the base 9 k is probably about an average-weight k for the 1k conjectures. Imagine what you would need to sieve for a low-weight k. But that one had already been searched to n=360K. For bases at n=100K, I think you'll be able to sieve n=100K-1M for some of them to get a 70% chance of prime, although many will need n=100K-2M I think. Iirc, for the lowest k on Riesel base 3, KEP said he had a 58-60% chance of prime for n=100K-1M, although he did not find one. And that's base 3, which is a far heavier-weight base than all others (although that doesn't necessarily mean the k that he tested is higher than the average k remaining on the 1k bases).

Gary

Last fiddled with by gd_barnes on 2010-06-24 at 08:22

 2010-06-24, 10:03 #69 Flatlander I quite division it     "Chris" Feb 2005 England 207710 Posts Okay, thanks. I'll have to think about some of that. I guessed the sieve files needed to be quiet high to get a >50% probability but I didn't guess that high. I'll continue with the program anyway. It will be interesting to see the stats and maybe a few will be easier to sieve for efficiently than others. Last fiddled with by Flatlander on 2010-06-24 at 10:04
2010-06-25, 06:13   #70
gd_barnes

"Gary"
May 2007
Overland Park, KS

22·11·269 Posts

Quote:
 Originally Posted by Flatlander Okay, thanks. I'll have to think about some of that. I guessed the sieve files needed to be quiet high to get a >50% probability but I didn't guess that high. I'll continue with the program anyway. It will be interesting to see the stats and maybe a few will be easier to sieve for efficiently than others.
I'll clarify on that:

What I was quoting was more like a probability of prime closer to 70%. Honestly I don't know what percentage chance of prime is the best to sieve. Also, the S9 example had already been tested to n=360K, meaning we'd need a much larger n-range to have a 70% chance of prime; hence why I gave the estimated range of n=360K-3M.

But if all you are looking for is a chance of 50% for a single k that is already tested to n=100K, I would guess, on average, you would need to sieve the range of n=100K to n=~1M or 1.5M somewhere. In giving that as a SWAG, I'm using KEP's estimate of 55-60% chance of prime for the lowest remaining Riesel base 3 k for n=100K-1M; which I independently confirmed as close to accurate for that particular k. But base 3 is heavier weight, on average, than all other bases, so I'm assuming that, on average, for other 1k bases, you'll need to sieve a larger range, even to have a 50% chance of prime.

If there any wonder why the final k's are so hard to find a prime for, this example demonstrates why. It's because they are usually one of the lowest weight remaining k's for the base.

Tell you what: You have me curious now. I'll manually calculate these for several 1k bases at n=100K. I'll also give the value of A discussed in the last posting for n=100K-200K, 200K-300K, and 300K-400K as well as n=1.8M-1.9M and 1.9M-2M for future reference. To get a fairly accurate value of A, I'll manually break up each n=100K range into 100 n=1K pieces.

Gary

Last fiddled with by gd_barnes on 2010-06-25 at 06:14

 2010-06-26, 23:26 #71 Flatlander I quite division it     "Chris" Feb 2005 England 31×67 Posts The program is working and producing stats that look about right. At the moment I have average-n fixed at the 40% of range mark and 'partitions' of 25k. This is what I have for S bases 266, 335, 337 and 341 (btw 341 and 337 are out of order in the 1k left thread 1st post.) S266 looks do-able but the rest are pretty depressing! Code: 100000000:P:1:266:257 Estimated probabilities of success for a sieve starting from 25001 : Probability for a sieve to 50008 is :0.3046898 Probability for a sieve to 75008 is :0.4392762 Probability for a sieve to 100008 is :0.5179446 Probability for a sieve to 125006 is :0.5703353 Probability for a sieve to 150006 is :0.6103485 Probability for a sieve to 175026 is :0.6401508 Probability for a sieve to 200054 is :0.663662 Probability for a sieve to 225002 is :0.6832097 Probability for a sieve to 250008 is :0.6996617 Probability for a sieve to 275018 is :0.7137238 Probability for a sieve to 300002 is :0.7264972 Probability for a sieve to 325004 is :0.7375231 Probability for a sieve to 350012 is :0.747241 Probability for a sieve to 375008 is :0.756104 Probability for a sieve to 400002 is :0.7638905 Probability for a sieve to 425030 is :0.7711558 Probability for a sieve to 450056 is :0.7778163 Probability for a sieve to 475004 is :0.7840917 Probability for a sieve to 500028 is :0.7896655 Probability for a sieve to 525014 is :0.7947405 Probability for a sieve to 550008 is :0.7994754 Probability for a sieve to 575006 is :0.8039504 Probability for a sieve to 600006 is :0.8081636 Probability for a sieve to 625004 is :0.812016 Probability for a sieve to 650006 is :0.8159369 Probability for a sieve to 675024 is :0.8195084 Probability for a sieve to 700022 is :0.8228505 Probability for a sieve to 725004 is :0.8259242 Probability for a sieve to 750018 is :0.8288481 Probability for a sieve to 775004 is :0.8316786 Probability for a sieve to 800010 is :0.8344177 Probability for a sieve to 825002 is :0.8369706 Probability for a sieve to 850002 is :0.8393937 Probability for a sieve to 875008 is :0.841714 Probability for a sieve to 900012 is :0.8440081 Probability for a sieve to 925002 is :0.8461736 Probability for a sieve to 950006 is :0.8482533 Probability for a sieve to 975006 is :0.8502517 Probability for a sieve to 999986 is :0.8521671 100000000:P:1:335:257 Estimated probabilities of success for a sieve starting from 25001 : Probability for a sieve to 50010 is :0.1355928 Probability for a sieve to 75042 is :0.2004586 Probability for a sieve to 100002 is :0.2464792 Probability for a sieve to 125006 is :0.2789975 Probability for a sieve to 150018 is :0.3062804 Probability for a sieve to 175002 is :0.3266961 Probability for a sieve to 200046 is :0.345123 Probability for a sieve to 225002 is :0.3605122 Probability for a sieve to 250038 is :0.3740461 Probability for a sieve to 275010 is :0.3856604 Probability for a sieve to 300020 is :0.396175 Probability for a sieve to 325092 is :0.4056267 Probability for a sieve to 350046 is :0.4147946 Probability for a sieve to 375002 is :0.4228382 Probability for a sieve to 400010 is :0.4302676 Probability for a sieve to 425010 is :0.4371182 Probability for a sieve to 450122 is :0.4434187 Probability for a sieve to 475034 is :0.4494008 Probability for a sieve to 500022 is :0.4548441 Probability for a sieve to 525008 is :0.4599947 Probability for a sieve to 550058 is :0.4651467 Probability for a sieve to 575090 is :0.4697821 Probability for a sieve to 600006 is :0.4742179 Probability for a sieve to 625034 is :0.4783694 Probability for a sieve to 650006 is :0.4824371 Probability for a sieve to 675014 is :0.4863998 Probability for a sieve to 700002 is :0.4900967 Probability for a sieve to 725040 is :0.4934128 Probability for a sieve to 750086 is :0.4969392 Probability for a sieve to 775038 is :0.500267 Probability for a sieve to 800042 is :0.5034002 Probability for a sieve to 825038 is :0.5064179 Probability for a sieve to 850026 is :0.5092647 Probability for a sieve to 875016 is :0.5120611 Probability for a sieve to 900054 is :0.5148096 Probability for a sieve to 925058 is :0.5174348 Probability for a sieve to 950066 is :0.5200572 Probability for a sieve to 975006 is :0.5225922 Probability for a sieve to 999962 is :0.5249875 100000000:P:1:337:257 Estimated probabilities of success for a sieve starting from 25001 : Probability for a sieve to 50013 is :0.1454151 Probability for a sieve to 75005 is :0.2250329 Probability for a sieve to 100049 is :0.2736259 Probability for a sieve to 125017 is :0.3094109 Probability for a sieve to 150017 is :0.3368471 Probability for a sieve to 175045 is :0.3600681 Probability for a sieve to 200049 is :0.3794001 Probability for a sieve to 225045 is :0.3961254 Probability for a sieve to 250089 is :0.4104187 Probability for a sieve to 275009 is :0.4235383 Probability for a sieve to 300045 is :0.4347367 Probability for a sieve to 325005 is :0.445013 Probability for a sieve to 350017 is :0.4543006 Probability for a sieve to 375049 is :0.4628028 Probability for a sieve to 400005 is :0.4709361 Probability for a sieve to 425013 is :0.4781026 Probability for a sieve to 450045 is :0.4850882 Probability for a sieve to 475025 is :0.4914963 Probability for a sieve to 500009 is :0.497448 Probability for a sieve to 525077 is :0.5028558 Probability for a sieve to 550009 is :0.508113 Probability for a sieve to 575109 is :0.5131022 Probability for a sieve to 600017 is :0.5178083 Probability for a sieve to 625013 is :0.5222524 Probability for a sieve to 650069 is :0.5265204 Probability for a sieve to 675005 is :0.5304789 Probability for a sieve to 700005 is :0.5342233 Probability for a sieve to 725013 is :0.5380203 Probability for a sieve to 750025 is :0.5416164 Probability for a sieve to 775009 is :0.5451453 Probability for a sieve to 800025 is :0.5483705 Probability for a sieve to 825025 is :0.5515493 Probability for a sieve to 850049 is :0.5546204 Probability for a sieve to 875013 is :0.5575707 Probability for a sieve to 900037 is :0.5604132 Probability for a sieve to 925057 is :0.5631033 Probability for a sieve to 950037 is :0.565847 Probability for a sieve to 975005 is :0.5684015 Probability for a sieve to 999989 is :0.570884 100000000:P:1:341:257 Estimated probabilities of success for a sieve starting from 25001 : Probability for a sieve to 50022 is :0.1208785 Probability for a sieve to 75048 is :0.1858103 Probability for a sieve to 100008 is :0.2279986 Probability for a sieve to 125016 is :0.25898 Probability for a sieve to 150024 is :0.2834809 Probability for a sieve to 175008 is :0.303843 Probability for a sieve to 200010 is :0.3207383 Probability for a sieve to 225036 is :0.3358499 Probability for a sieve to 250044 is :0.3486327 Probability for a sieve to 275004 is :0.3599488 Probability for a sieve to 300006 is :0.3701751 Probability for a sieve to 325032 is :0.3792854 Probability for a sieve to 350016 is :0.3877428 Probability for a sieve to 375054 is :0.3954519 Probability for a sieve to 400110 is :0.4024843 Probability for a sieve to 425034 is :0.4092336 Probability for a sieve to 450030 is :0.4152985 Probability for a sieve to 475020 is :0.4208208 Probability for a sieve to 500070 is :0.4261296 Probability for a sieve to 525006 is :0.431372 Probability for a sieve to 550020 is :0.4361647 Probability for a sieve to 575004 is :0.4405598 Probability for a sieve to 600072 is :0.4447985 Probability for a sieve to 625038 is :0.4490166 Probability for a sieve to 650016 is :0.4527816 Probability for a sieve to 675036 is :0.456551 Probability for a sieve to 700026 is :0.4604775 Probability for a sieve to 725070 is :0.4638947 Probability for a sieve to 750072 is :0.4671016 Probability for a sieve to 775008 is :0.470193 Probability for a sieve to 800004 is :0.4732406 Probability for a sieve to 825030 is :0.4761627 Probability for a sieve to 850056 is :0.479094 Probability for a sieve to 875010 is :0.4817891 Probability for a sieve to 900102 is :0.4844173 Probability for a sieve to 925050 is :0.4869543 Probability for a sieve to 950004 is :0.4895191 Probability for a sieve to 975018 is :0.491972 Probability for a sieve to 999942 is :0.4943631 Do these look about right? When you give me details of the best way to set average-n, I will program it in. (In the meantime I'll probably start adding some code now to work through the S and R lists producing probability files.)
 2010-06-27, 00:35 #72 gd_barnes     "Gary" May 2007 Overland Park, KS 22·11·269 Posts Mark, I'm sorry, I've lost where the posting is now. Can you post a link to the latest version of srfile that can remove many k's at once? It would be very handy for a new effort that I am working on. Thanks, Gary
 2010-06-27, 01:17 #73 kar_bon     Mar 2006 Germany 2,999 Posts The link was in the 33-100 base thread (post #666). Use srsieve V0.6.17 which includes srfile with the new option.
 2010-09-10, 09:08 #74 gd_barnes     "Gary" May 2007 Overland Park, KS 22×11×269 Posts Tim, You had provided a link to all of the needed CRUS software that I put in the 1st posting of this thread. The link does not seem to work now. Can you provide a new link or an attachment to the programs that I can upload to my server machine so that I can provide a link. Gary
 2010-09-10, 09:16 #75 kar_bon     Mar 2006 Germany BB716 Posts Worked for me here! But the ZIP-files contains all older versions! @Gary: If you plan to create such download on the CRUS-page, please include the script-file "new-bases-4.3.txt" and perhaps other tiny scripts/tools, too! Last fiddled with by kar_bon on 2010-09-10 at 09:19
2010-09-10, 09:37   #76
gd_barnes

"Gary"
May 2007
Overland Park, KS

22×11×269 Posts

Quote:
 Originally Posted by kar_bon Worked for me here! But the ZIP-files contains all older versions! @Gary: If you plan to create such download on the CRUS-page, please include the script-file "new-bases-4.3.txt" and perhaps other tiny scripts/tools, too!
Not for me. When I click on the word "here" in:

If you can post an attachment with the programs, I'll add the starting bases script to it and upload the whole thing to my machine and provide a new link for it.

Gary

 2010-09-10, 10:08 #77 kar_bon     Mar 2006 Germany 56678 Posts I've just uploaded it here and contains (6.0 MB): - LLR / cLLR V3.8.1 - PFGW WIN V3.5 and V3.6 - sr1sieve V1.4.1 - sr2sieve V1.8.11 - srsieve / srfile V0.6.17 - PFGW-script "new-bases-4.3.txt"

 Similar Threads Thread Thread Starter Forum Replies Last Post __HRB__ Programming 41 2012-07-07 17:43 WraithX GMP-ECM 37 2011-10-28 01:04 gd_barnes No Prime Left Behind 48 2009-07-31 01:44 OmbooHankvald PSearch 3 2005-08-05 20:28 jasong Sierpinski/Riesel Base 5 10 2005-03-14 04:03

All times are UTC. The time now is 10:37.

Sun Feb 5 10:37:54 UTC 2023 up 171 days, 8:06, 1 user, load averages: 0.40, 0.71, 0.71