mersenneforum.org Odds that a random number is prime
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-27, 19:30 #1 Number theory   134410 Posts 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?
 2009-08-28, 00:26 #2 wblipp     "William" May 2003 New Haven 2,371 Posts 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
2009-08-28, 11:26   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Number theory 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.

 2009-08-28, 16:50 #4 Bearnol2   3·11·157 Posts --- In primenumbers@yahoogroups.com, James Wanless 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
 2009-08-28, 22:04 #5 Number theory   76F16 Posts Thanks.

 Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Homework Help 60 2010-10-13 10:31 jasong jasong 32 2009-12-01 06:43 Greenk12 Factoring 1 2008-11-15 13:56 Orgasmic Troll Lounge 6 2007-08-11 04:09 ewmayer Lounge 10 2007-08-01 20:11

All times are UTC. The time now is 10:33.

Tue May 17 10:33:33 UTC 2022 up 33 days, 8:34, 0 users, load averages: 0.88, 0.85, 0.88