mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)

 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

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

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:

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 21:59.