mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2013-09-17, 21:25   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

256616 Posts
Default 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|n
2. 10% of the range was checked and 1 prime was found. How many more primes does one expect to find?
Batalov is offline   Reply With Quote
Old 2013-09-17, 21:57   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
Mini-Geek is offline   Reply With Quote
Old 2013-09-17, 22:29   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts
Default

I get:
  1. 2.1066704325
  2. (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
Mini-Geek is offline   Reply With Quote
Old 2013-09-17, 23:04   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

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.)
Batalov is offline   Reply With Quote
Old 2016-08-10, 23:27   #5
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

1,483 Posts
Default

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?
pepi37 is offline   Reply With Quote
Old 2016-08-11, 01:17   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

501010 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Status page with expected number of Mersenne primes in each interval? CRGreathouse PrimeNet 2 2018-01-10 06:13
Expected number of primes in OEIS A007908 ewmayer Probability & Probabilistic Number Theory 6 2015-11-10 16:33
I get 13% less primes than I expected:-( mart_r Math 2 2010-10-29 17:31
Twin primes expected first k formula robert44444uk Math 18 2008-04-02 21:19
Expected Number of Factors for numbers within a ra grandpascorpion Math 2 2007-12-17 13:48

All times are UTC. The time now is 08:08.


Wed Oct 27 08:08:33 UTC 2021 up 96 days, 2:37, 0 users, load averages: 1.15, 0.99, 0.97

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.