mersenneforum.org > Math Generating Random Primes
 Register FAQ Search Today's Posts Mark Forums Read

 2008-04-22, 17:58 #1 davar55     May 2004 New York City 23×232 Posts Generating Random Primes This is a naive question: Suppose I want to generate an N-digit prime. I pick an M > N, generate a (random) M-digit number (by choosing M random digits), and then try to factor M. What is the probabilty that such a random M-digit number has an N-digit prime factor (as a function of M and N)?
 2008-04-22, 21:34 #2 wblipp     "William" May 2003 New Haven 3·787 Posts If M is a "lot" larger then N, then M doesn't matter and the probability at least one factor between 10N-1 and 10N 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
 2010-12-27, 20:25 #3 davar55     May 2004 New York City 23·232 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?
2010-12-27, 20:46   #4
axn

Jun 2003

23·607 Posts

Quote:
 Originally Posted by davar55 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?
I would think that that is a false statement. It is quite conceivable that we would not have, for example, a 9-digit exponent yielding a mersenne prime.

 2010-12-27, 21:04 #5 davar55     May 2004 New York City 23·232 Posts Well, if we could PROVE a lower bound of 1.1 say, and a higher bound of ten (10.000) for the ratio Mn+1/Mn, 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".
2010-12-27, 21:10   #6
axn

Jun 2003

485610 Posts

Quote:
 Originally Posted by davar55 The trick is, prove a better lower bound and prove 10 is an upper bound.
For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?

Quote:
 Originally Posted by davar55 Note I said "can anyone" not "I can here".
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]

2010-12-27, 21:17   #7
davar55

May 2004
New York City

23×232 Posts

Quote:
 Originally Posted by axn For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?
Yes, indeed.

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]
And that's the crux. I say there is, and it's < 10.

But you don't have to take that on faith ...

2010-12-27, 22:02   #8
CRGreathouse

Aug 2006

10111010101002 Posts

Quote:
 Originally Posted by davar55 In particular, first, can anyone show why every digit range 10^n to 10^(n+1)-1 must contain at least one Mersenne Prime?
The expected number of Mersenne primes in such a range is $e^\gamma\lg10\approx5.9,$ 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.

 2010-12-27, 23:51 #9 davar55     May 2004 New York City 23·232 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".
2010-12-28, 00:06   #10
CRGreathouse

Aug 2006

175416 Posts

Quote:
 Originally Posted by davar55 Your basic assumption is random process, which is incorrect. I make no such necessary assumption in my "guess".
I trust you disbelieve the Prime Number Theorem, then? My statement could be made precise, with no use of randomness, just as the PNT can be. It's common to phrase the PNT in probabilistic terms because it's convenient and mathematicians know how to convert from the informal to the formal versions when needed.

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 epsilon-delta transformation for you. Of course the result will be every bit as conjectural as the original version.

 2010-12-28, 00:20 #11 davar55     May 2004 New York City 23×232 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 YJ-Conjecture will prove to be a lemma in the proof of the infinitude of the Mersenne Primes. Anti-crankness forbids any grander claims here.

 Similar Threads Thread Thread Starter Forum Replies Last Post danaj Programming 17 2017-09-15 16:41 jasong Lounge 46 2017-05-09 12:32 Greenk12 Factoring 1 2008-11-15 13:56 Wacky Puzzles 46 2005-06-05 22:19 wblipp Software 2 2005-01-05 13:29

All times are UTC. The time now is 01:59.

Fri Feb 26 01:59:00 UTC 2021 up 84 days, 22:10, 0 users, load averages: 2.06, 1.64, 1.54