mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   The expected number of primes (https://www.mersenneforum.org/showthread.php?t=18601)

Batalov 2013-09-17 21:25

The expected number of primes
 
Here's a couple of easy exercises:

1. How many primes does one expect to find in the class k*10^n-1, where 2<=k<=9 and 1000000<=n<1250000.[INDENT]Hints for the small adjustments of probabilites:[INDENT]a) [SPOILER]k is in {2,3, 5,6, 8,9}[/SPOILER]
b) [SPOILER]for k=8, remove n :: 3|n; for k=9, remove n :: 2|n[/SPOILER][/INDENT][/INDENT]
2. 10% of the range was checked and 1 prime was found. How many more primes does one expect to find?

Mini-Geek 2013-09-17 21:57

[QUOTE=Batalov;353273]2. 10% of the range was checked and 1 prime was found. How many more primes does one expect to find?[/QUOTE]

Shall we assume that is the first 10% by n, i.e. 1000000<=n<1025000, or something else?

Mini-Geek 2013-09-17 22:29

I get:[LIST=1][*][SPOILER]2.1066704325[/SPOILER][*](assuming my definition of "10%" from my last post) [SPOILER]1.8736586992[/SPOILER][/LIST][SPOILER]That means that eliminating 10% of the candidates reduced the expected primes remaining by about 11%. The expected primes for the whole range has gone up to ~2.87, since we found 1 prime.
I sieved to 100000 to get my figures. If you sieve to any other amount, you may get slightly different figures.[/SPOILER]

I'm rusty at this sort of thing, but I used to do this often, so I'm fairly confident that I'm correct. :smile:

Batalov 2013-09-17 23:04

Hmm, yes, roughly the lowest n values, for simplicity.

(IRL, there was a small scale survey of speeds all over the rectangle, but this was a small portion. Such a survey is helpful to be prepared for FFT length shifts, which are different for different k values.)

pepi37 2016-08-10 23:27

Expected number of primes is expected after all. :smile:
But in RL, on what number of primes I "must" set a goal to find at least one but for sure!
I am sure that was countless combination where was expected one or two primes, but found nothing in range.
So real question is: how to increase chances to find prime in range: to take more K and do less range or take less K but make wide range?

VBCurtis 2016-08-11 01:17

[QUOTE=pepi37;439769]
So real question is: how to increase chances to find prime in range: to take more K and do less range or take less K but make wide range?[/QUOTE]

Yes. Or, both. Or no, if the "less" outweighs the "more". You're asking a math question but not using quantities- so, as usual, it depends on the quantities.

A list of primality tests are independent events- so, whatever you do to increase the number of expected primes in your 'range', that should also increase your probability of finding a single prime.

If your interests include amount of time to find a prime, you're better off with more k's rather than extending to a higher range, because larger candidates take longer to test but are less likely per-test to be prime.


All times are UTC. The time now is 17:40.

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