mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2009-08-27, 19:30   #1
Number theory
 

3·2,689 Posts
Default Odds that a random number is prime

A random 321,000 (decimal) digit number is chosen. What is the probability that it's prime if it...

a.) Is an odd number?
b.) Doesn't have any factors below one billion (10^9)?
c.) Doesn't have any factors below one trillion (10^12)?

For part A, I got 1 in 370,000 by taking ln(10^321000) and dividing it by 2. Is this right? Also, could you help me out with parts B and C?
  Reply With Quote
Old 2009-08-28, 00:26   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

94116 Posts
Default

http://en.wikipedia.org/wiki/Mertens%27_theorems

The third theorem is usually rearranged to get an estimate.

Last fiddled with by wblipp on 2009-08-28 at 00:26
wblipp is offline   Reply With Quote
Old 2009-08-28, 11:26   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Number theory View Post
A random 321,000 (decimal) digit number is chosen. What is the probability that it's prime if it...

a.) Is an odd number?
b.) Doesn't have any factors below one billion (10^9)?
c.) Doesn't have any factors below one trillion (10^12)?

For part A, I got 1 in 370,000 by taking ln(10^321000) and dividing it by 2. Is this right? Also, could you help me out with parts B and C?
(a) 2* [pi(10^321000) - pi(10^320999)]/(10^321000 - 10^320999)

(b) approx. exp(gamma)/[9 * log(10)]

(c) approx. exp(gamma)/[12*log(10)]

Where pi is the prime counting function and gamma is Euler's constant.
Look up Mertens' Theorem.

Your answer for (a) is approximately correct.
R.D. Silverman is offline   Reply With Quote
Old 2009-08-28, 16:50   #4
Bearnol2
 

5·29·41 Posts
Default

--- In primenumbers@yahoogroups.com, James Wanless <james@...> wrote:

Hello All,
I am interested in trying to derive (an estimate of) an expression for
the likelihood [expressed as a probability between 0 and 1] that a given
generic number (eg random) N is prime, given that no factors of it have
yet been found of a size up to some lesser integer, M.
I found this expression, which makes use of Merten's Theorem:
http://home.earthlink.net/~elevensmo....html#Residual
However, on first seeing Merten's Theorem I (mistakenly?) assumed that
this _in itself_ [ie in entirety] was the answer I needed above, rather
than the somewhat more complex answer in the link. I also (mistakenly?)
had guestimated to myself (on very first thoughts) that my required
expression might actually be independent of N [so long as within certain
limits, eg M<=sqrt(N)].
Note that this is pretty much the case with pure Merten's.
Surely, therefore, what I am saying is that the expression in the link
is too simplistic [or rather actually over-complex], because, for
instance, it does not take into account the fact that not all primes in
its population under consideration are equally likely - in fact the
larger ones will be much rarer, probability-wise.
Am I going nuts here, or can someone else see what I'm getting at?
[obviously - for my nefarious purposes :-) - ie gaining some evidence
that MM127 is prime :-) - I'm looking for a probability answer as high
as possible, but I do genuinely believe atm that the currently accepted
estimate is too low...]
Please help!
James

Firstly, thanks for your input regarding this, folks...
I too have been thinking about it a bit more, and this, I think is my
query/problem/objection:
********************************************************************
Suppose you give me a supposedly 'random' integer N.
Suppose I then discover (empirically) that it is not divisible by any
number (or indeed prime number) less than say 1000000 [ie M=1000000]
Am I not entitled to be surprised - _regardless_ of the size of number N
you originally gave me?
********************************************************************
ie - just a 'pure' Mertens result - rather than the lowering adjustment
to Mertens...
(IMHO) Probability is _so_ tricky, so I'm not claiming infallibility
here, by any means - but I'd really appreciate it if someone could clear
this up for me!


I _think_ I might finally have an answer to this (after much consideration...)??
[Mertens' theorem is a red-herring to this situation]
*********************************************
pr(N prime | no factors up to M)
= ln (M^2) / ln N
*********************************************
J

...which would mean that the 'surprise factor' to discover that N has no factors up to M _would_ be independent of N, and just:
******************************
ln (M^2)
******************************
Now how exactly one interprets that 'surprise factor'...?
J
  Reply With Quote
Old 2009-08-28, 22:04   #5
Number theory
 

25×132 Posts
Default

Thanks.
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odds that a Random Prime is a Number? R.D. Silverman Homework Help 60 2010-10-13 10:31
odds of random number being prime jasong jasong 32 2009-12-01 06:43
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56
Odds of a prime number being random Orgasmic Troll Lounge 6 2007-08-11 04:09
odds of a random prime being a number ewmayer Lounge 10 2007-08-01 20:11

All times are UTC. The time now is 15:11.


Mon Nov 29 15:11:54 UTC 2021 up 129 days, 9:40, 0 users, load averages: 1.90, 1.59, 1.44

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.