20080422, 17:58  #1 
May 2004
New York City
2×2,099 Posts 
Generating Random Primes
This is a naive question:
Suppose I want to generate an Ndigit prime. I pick an M > N, generate a (random) Mdigit number (by choosing M random digits), and then try to factor M. What is the probabilty that such a random Mdigit number has an Ndigit prime factor (as a function of M and N)? 
20080422, 21:34  #2 
"William"
May 2003
New Haven
100100100100_{2} Posts 
If M is a "lot" larger then N, then M doesn't matter and the probability at least one factor between 10^{N1} and 10^{N} is 1/N. Here's how I explained it in the ElevenSmooth FAQ
http://elevensmooth.com/MathFAQ.html#NoFactors This heuristic breaks down when N gets close to M because you cannot have two 40 digit factors of a 50 digit number. For M < 2N you can use the Dickman function to find the probability the largest prime divisor exceeds N and N+1 digits. http://mathworld.wolfram.com/DickmanFunction.html for 2N < M < 3N the corresponding function for second largest divisor can be used. It's heuristically derived in this thread, with confirmation by Brent. http://www.mersenneforum.org/showthread.php?t=2996 William 
20101227, 20:25  #3 
May 2004
New York City
2·2,099 Posts 
I never thought to ask myself the similar question for Mersenne Primes.
In particular, first, can anyone show why every digit range 10^n to 10^(n+1)1 must contain at least one Mersenne Prime? 
20101227, 20:46  #4 
Jun 2003
1001010101000_{2} Posts 
I would think that that is a false statement. It is quite conceivable that we would not have, for example, a 9digit exponent yielding a mersenne prime.

20101227, 21:04  #5 
May 2004
New York City
1000001100110_{2} Posts 
Well, if we could PROVE a lower bound of 1.1 say, and a higher bound
of ten (10.000) for the ratio M_{n+1}/M_{n}, that would imply the truth of my suggestion. It would also prove that M.primes go on forever. The trick is, prove a better lower bound and prove 10 is an upper bound. Note I said "can anyone" not "I can here". 
20101227, 21:10  #6  
Jun 2003
2^{3}×3×199 Posts 
Quote:
Yes. I was betting on no one being able to prove it  i.e. there is no fixed upper bound for Mn+1/Mn [actually this is a stronger statement than is probably needed] 

20101227, 21:17  #7  
May 2004
New York City
2·2,099 Posts 
Quote:
Quote:
But you don't have to take that on faith ... 

20101227, 22:02  #8 
Aug 2006
2·2,969 Posts 
The expected number of Mersenne primes in such a range is so the chance of a given such interval having no Mersenne primes is about 0.27%. Any 257 disjoint intervals would have about a 50% chance of having at least one failing to have any Mersenne primes. So it's more likely than not (assuming present understanding) that by 10^265 the conjecture will fail, and by 10^2577 it's 99.9% likely.

20101227, 23:51  #9 
May 2004
New York City
4198_{10} Posts 
And by 10^googolplex it's 99.99999999999999999999 % likely.
So what? Your basic assumption is random process, which is incorrect. I make no such necessary assumption in my "guess". 
20101228, 00:06  #10  
Aug 2006
2×2,969 Posts 
Quote:
Of course the statement itself is conjectural, which makes the informality all the more sensible. But if you can't figure out what a nonrandom version of the statement would look like, I can provide an epsilondelta transformation for you. Of course the result will be every bit as conjectural as the original version. 

20101228, 00:20  #11 
May 2004
New York City
2·2,099 Posts 
I accept the PNT as proven, and I believe the RH is on the
verge of being proven. Randomness is an approximation to the prime distribution, and can and must be removed from any final proof of these two theorems. I think my YJConjecture will prove to be a lemma in the proof of the infinitude of the Mersenne Primes. Anticrankness forbids any grander claims here. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generating a uniform random nbit semiprime  danaj  Programming  17  20170915 16:41 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 
Generating 2005  Wacky  Puzzles  46  20050605 22:19 
Generating Small Primes  wblipp  Software  2  20050105 13:29 