mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-04-22, 17:58   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default 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)?
davar55 is offline   Reply With Quote
Old 2008-04-22, 21:34   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001001002 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2010-12-27, 20:25   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

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?
davar55 is offline   Reply With Quote
Old 2010-12-27, 20:46   #4
axn
 
axn's Avatar
 
Jun 2003

10010101010002 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
axn is online now   Reply With Quote
Old 2010-12-27, 21:04   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

10000011001102 Posts
Default

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".
davar55 is offline   Reply With Quote
Old 2010-12-27, 21:10   #6
axn
 
axn's Avatar
 
Jun 2003

23×3×199 Posts
Default

Quote:
Originally Posted by davar55 View Post
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 View Post
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]
axn is online now   Reply With Quote
Old 2010-12-27, 21:17   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

Quote:
Originally Posted by axn View Post
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 ...
davar55 is offline   Reply With Quote
Old 2010-12-27, 22:02   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-27, 23:51   #9
davar55
 
davar55's Avatar
 
May 2004
New York City

419810 Posts
Default

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".
davar55 is offline   Reply With Quote
Old 2010-12-28, 00:06   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-28, 00:20   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

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.
davar55 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generating a uniform random n-bit semiprime danaj Programming 17 2017-09-15 16:41
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56
Generating 2005 Wacky Puzzles 46 2005-06-05 22:19
Generating Small Primes wblipp Software 2 2005-01-05 13:29

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

Tue Nov 24 07:01:00 UTC 2020 up 75 days, 4:11, 4 users, load averages: 2.08, 1.82, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.