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)?

If M is a "lot" larger then N, then M doesn't matter and the probability at least one factor between 10[sup]N-1[/sup] and 10[sup]N[/sup] is 1/N. Here's how I explained it in the ElevenSmooth FAQ

[URL="http://elevensmooth.com/MathFAQ.html#NoFactors"]http://elevensmooth.com/MathFAQ.html#NoFactors[/URL]


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.

[URL="http://mathworld.wolfram.com/DickmanFunction.html"]http://mathworld.wolfram.com/DickmanFunction.html[/URL]


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.

[URL="http://www.mersenneforum.org/showthread.php?t=2996"]http://www.mersenneforum.org/showthread.php?t=2996[/URL]

William

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?

[QUOTE=davar55;243531]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?[/QUOTE]

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.

Well, if we could PROVE a lower bound of 1.1 say, and a higher bound
of ten (10.000) for the ratio M[sub]n+1[/sub]/M[sub]n[/sub], 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".

[QUOTE=davar55;243537]The trick is, prove a better lower bound and prove 10 is an upper bound.[/quote]
For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?

[QUOTE=davar55;243537]Note I said "can anyone" not "I can here".[/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]

[QUOTE=axn;243539]For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?[/QUOTE]

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

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

[QUOTE=davar55;243531]In particular, first, can anyone show why every digit
range 10^n to 10^(n+1)-1 must contain at least
one Mersenne Prime?[/QUOTE]

The expected number of Mersenne primes in such a range is [TEX]e^\gamma\lg10\approx5.9,[/TEX] 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. :smile:

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".

[QUOTE=davar55;243568]Your basic assumption is random process, which is
incorrect. I make no such necessary assumption in my "guess".[/QUOTE]

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.

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.