Odds of prime discussion

[TheCount]

Originally Posted by gd_barnes

On our "difficulty" stats, our programming guru, Mark (rogue), uses a sieve to P=1M, which is very clearly accurate enough for determing such a stat.

What range does rogue sieve for determining the "difficulty" stats? For Nash weight you sieve the range 100,001 to 110,000.

To determine the weight for a random number I can just sieve "k*n-1" for different k values (first 10,000 say) and find the average. srsieve does not support integer sequences of this type though.

I note R916 fell pretty quickly, and with a double hit.

[rogue]

Originally Posted by TheCount

What range does rogue sieve for determining the "difficulty" stats? For Nash weight you sieve the range 100,001 to 110,000.

To determine the weight for a random number I can just sieve "k*n-1" for different k values (first 10,000 say) and find the average. srsieve does not support integer sequences of this type though.

I note R916 fell pretty quickly, and with a double hit.

IIRC, it sieves to 1e6, but also eliminates numbers with algebraic factorizations. The difficulty is a rough guess to the number of tests needed at 1e12. The reason it sieves to 1e6 is because many of the k are larger than 1e5. It isn't perfect, but hopefully more accurate.

[gd_barnes]

Originally Posted by rogue

IIRC, it sieves to 1e6, but also eliminates numbers with algebraic factorizations. The difficulty is a rough guess to the number of tests needed at 1e12. The reason it sieves to 1e6 is because many of the k are larger than 1e5. It isn't perfect, but hopefully more accurate.

That's sieving P-depth. I think he wants to know what n-range that it sieves. In other words, does it sieve n=100001-110000 like for Nash weight? I'm not sure about that. Do you remember?

On the P-depth, it does sieve to P=1e6 and then uses a multiplier to estimate a sieve to P=1e12...and to me it's more than a "rough guess" on the number of tests at P=1e12. I've found it to be very accurate.

[rogue]

Originally Posted by gd_barnes

That's sieving P-depth. I think he wants to know what n-range that it sieves. In other words, does it sieve n=100001-110000 like for Nash weight? I'm not sure about that. Do you remember?

On the P-depth, it does sieve to P=1e6 and then uses a multiplier to estimate a sieve to P=1e12...and to me it's more than a "rough guess" on the number of tests at P=1e12. I've found it to be very accurate.

Yes, that is correct, it uses that range for n. It's good to know that you have found it to be very accurate. Of course you would have let me know if it were wildly off.

[TheCount]

OK, so the "n per 25000 at 1e12" value in the Unproven Conjectures table is derived by calling:
> srsieve -n 100001 -N 110000 -P 1e6 "k*b^n+/-1"
For each k, multiplying the results by 1.25, and adding them all together.

The point is that P=1e6 gives a more accurate weight than P=511, so I will use that from now on.

[gd_barnes]

Originally Posted by TheCount

OK, so the "n per 25000 at 1e12" value in the Unproven Conjectures table is derived by calling:
> srsieve -n 100001 -N 110000 -P 1e6 "k*b^n+/-1"
For each k, multiplying the results by 1.25, and adding them all together.

The point is that P=1e6 gives a more accurate weight than P=511, so I will use that from now on.

To clarify, he runs srsieve only one time for each base, which sieves all k's at once usually in just a few seconds. There is no multiple runs for all k's followed by adding them all together. Actually, srsieve gets run once only for bases that have changed since the last time the page was updated. It's very efficient.

[TheCount]

Part of the reason I like prime finding is the fun of learning some new maths and number theory.
In the Proth/Riesel probability equation I am working on the weight w was the Nash weight divided by 1751.542 giving a coefficient of 1.00 for the average k of base 2.
The trouble with that is it assumes base 2 has the same density of primes as a randomly chosen set of odd numbers of the same magnitude.
So I want to find weight of the a randomly chosen set of odd numbers of the same magnitude as k*b^n-1.
How to go about that?

I tried by finding the weight of the term k*n-1.
I could just average sieve runs for the first 100,000 k's but sieve programs don't deal with the term k*n-1.
Instead I used Prime Number Theory which says that the chance of a random integer x being prime is about 1/log x
For x = k*n-1, chance is about 1/log (k*n-1)

To find the probability for a fixed k over a given range we integrate from n = A to n = B.
Integrating 1/log (k*n-1) gives li(k*n-1)/k, where li() is the logarithmic integral.
So the number of primes, or fraction thereof, expected in a given range n = A to B for k*n-1 is:
(li(k*B-1)-li(k*A-1))/k

There is a logarithmic integral calculator here:
http://keisan.casio.com/exec/system/1180573428

Now I use this for R620, where b=620 and k=20.
The Unproven Conjectures table has the P=1e6 weights in the n per 25000 at 1e12 column if you divide by 1.25.
For R620 the P=1e6 weight is 1007/1.25=805.6
The weight of the term 20*n-1 is (li(k*B-1)-li(k*A-1))/k = (li(20*110000-1)-li(20*100001-1))/20 = 686.885
So w = 805.6/686.885 = 1.1728

This compares to my old version where the Nash weight was 1855, so w = 1855/1751.542 = 1.0591

So the probability increases from 11.42% to 12.64% using this new w.
This is still too low compared to 19.5%. I'll have to keep thinking on it.

[henryzz]

TheCount's calculations fail for b != 2 as base 2 is assumed in the calculation of 1751.

I have spent today delving though the paper linked in http://www.mersenneforum.org/showpos...3&postcount=34 and have implemented the method it uses in the spreadsheet. It produces the same results as the original method.
I also extended both methods to support ranges of n based on integration. At some point in the future I might add ranges of k as well.

In the attached spreadsheet the first tab is the original method. The second is the new method and also includes a proth weight calculation. It wouldn't surprise me if either the new or old methods have regions where they give better/worse estimates than the other. If you find they are different for certain input then please let me know. I have been unable to find an example.
I left it set up for R620 using Gary's data sieved to 5T.

[TheCount]

Thanks for that post henryzz. I will read the paper you linked to see what a real Mathematician thinks.

I noted with the integrated probability equation that if you make the reasonable assumptions: ln k << B ln b, and ln k << A ln b, (where w is the weight, b is the base, k is the k, testing range from n=A to n=B)
and use some logarithmic identities that the equation: #Primes = w * (ln(ln k + B*ln b) - ln(ln k + A*ln b))/ln b
becomes #Primes = w * log_bB/A
Quote a bit simpler!

Also I used the term k*b*n-1 for the weight of a random set of odd numbers of the same magnitude and I got 18.23% for R620. Much closer to 19.5%.
I'll compare all the 1 k's for the old and new methods in your spreadsheet and see what I can find.

[henryzz]

In this kind of spreadsheet formula simplification of that form isn't necessary. I would prefer the accuracy myself.

[TheCount]

Well, I completed checking the probability formulas for the 1k's. What I found is that:
- henryzz new method is the same as the old. Same inputs and results.
- these methods require the range to be pre-sieved. Only 21% of the 1k's are sieved.
- my new method don't require pre-sieving and is 98.9% correlated on the Riesel side and 97.0% correlated on the Sierpinski side.
- I don't know which method is more accurate.

The weight (w) I used in the spreadsheet column O, attached, is:
w = k*b*P_1e6 / (li(110,000*k*b)-li(100,001*k*b))

Where li(x) ∼ x/ln(x) + x/ln(x)² + 2x/ln(x)³ + 6x/ln(x)⁴ + 24x/ln(x)⁵ + ...

CRUS - 1k's.zip

In the early 1970s, following a counting session, the Count would laugh maniacally, "AH AH AH AH AH!"