mersenneforum.org The expected number of primes
 Register FAQ Search Today's Posts Mark Forums Read

 2013-09-17, 21:25 #1 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33·367 Posts 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.Hints for the small adjustments of probabilites:a) k is in {2,3, 5,6, 8,9} b) for k=8, remove n :: 3|n; for k=9, remove n :: 2|n2. 10% of the range was checked and 1 prime was found. How many more primes does one expect to find?
2013-09-17, 21:57   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·3·23·31 Posts

Quote:
 Originally Posted by Batalov 2. 10% of the range was checked and 1 prime was found. How many more primes does one expect to find?
Shall we assume that is the first 10% by n, i.e. 1000000<=n<1025000, or something else?

Last fiddled with by Mini-Geek on 2013-09-17 at 22:30

 2013-09-17, 22:29 #3 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 2·3·23·31 Posts I get:2.1066704325 (assuming my definition of "10%" from my last post) 1.8736586992 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. I'm rusty at this sort of thing, but I used to do this often, so I'm fairly confident that I'm correct. Last fiddled with by Mini-Geek on 2013-09-17 at 22:31
 2013-09-17, 23:04 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 990910 Posts 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.)
 2016-08-10, 23:27 #5 pepi37     Dec 2011 After milion nines:) 23×3×5×13 Posts Expected number of primes is expected after all. 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?
2016-08-11, 01:17   #6
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

17×317 Posts

Quote:
 Originally Posted by pepi37 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?
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.

Last fiddled with by VBCurtis on 2016-08-11 at 01:21

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse PrimeNet 2 2018-01-10 06:13 ewmayer Probability & Probabilistic Number Theory 6 2015-11-10 16:33 mart_r Math 2 2010-10-29 17:31 robert44444uk Math 18 2008-04-02 21:19 grandpascorpion Math 2 2007-12-17 13:48

All times are UTC. The time now is 16:13.

Thu Aug 18 16:13:33 UTC 2022 up 13:42, 0 users, load averages: 1.42, 1.48, 1.46