mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)
-   -   Software/instructions/questions (https://www.mersenneforum.org/showthread.php?t=9742)

Flatlander 2010-06-23 19:09

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=gd_barnes;219430] For the n-value, use a little less than the average of the range; let's say n=140K.[/QUOTE]
Why 'a little less'?

gd_barnes 2010-06-24 08:14

[quote=Flatlander;219670]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'?[/quote]


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

Flatlander 2010-06-24 10:03

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 [I]that [/I]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.
:smile:

gd_barnes 2010-06-25 06:13

[quote=Flatlander;219742]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 [I]that [/I]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.
:smile:[/quote]

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

Flatlander 2010-06-26 23:26

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

[/CODE]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.)

gd_barnes 2010-06-27 00:35

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

kar_bon 2010-06-27 01:17

The [url=http://sites.google.com/site/geoffreywalterreynolds/programs/srsieve]link[/url] was in the 33-100 base thread (post #666).

Use srsieve V0.6.17 which includes srfile with the new option.

gd_barnes 2010-09-10 09:08

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

kar_bon 2010-09-10 09:16

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!

gd_barnes 2010-09-10 09:37

[quote=kar_bon;229265]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![/quote]

Not for me. When I click on the word "here" in:

"Click here to download your attachment" on the google sites page, I get "Internet Explorer cannot display the webpage". I've tried it 4 times. I'm using IE8 in Windows Vista.

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

kar_bon 2010-09-10 10:08

I've just uploaded it [url=www.rieselprime.de/dl/CRUS_pack.zip]here[/url] 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"


All times are UTC. The time now is 04:45.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.