20060126, 16:35  #12  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Random numbers and proper factors.
Quote:
"The Art of computer programming" by Donald E. Knuth who devotes some 150 pages on RN. You are now standing on level ground. Climb up on his shoulders and you will be able to see further. Mally 

20060126, 23:30  #13  
Nov 2005
2^{4}×3 Posts 
Quote:
"Let Pr(n) be the probability that three positive integers \leq n have no factors in common. Compute \lim_{n > \infty} Pr(n)." To produce a rigorous proof that this limit is in fact 1/zeta(3), you have to do a little bit of analysis. You have to double check that the series rearrangements you are doing are legal (they are) and that the error term goes to zero (it does). I was wondering if the details were written down somewhere. John 

20060127, 02:43  #14  
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
Quote:
it's briefly mentioned here. edited to add: http://primes.utm.edu/notes/relprime.html seriously, 5 minutes and google got me here. No wonder Bob gets so riled up. Last fiddled with by Orgasmic Troll on 20060127 at 02:45 

20060127, 03:50  #15  
Nov 2005
2^{4}·3 Posts 
Quote:


20060128, 10:33  #16  
Bronze Medalist
Jan 2004
Mumbai,India
2052_{10} Posts 
Random numbers and proper factors.
Quote:
Zeta (3) is now known as (Roger) Apery's number after he proved that it is irrational in 1978 and given the name in his honour. So the chances are the reciprocal of Apery' number. I/1.202056903159 =0.83190737258 =83% appx. For two random numbers the chances are appx. 61% (0.607927102 ) or 1/Z(2) = 6/pi^2 Mally 

20060201, 02:48  #17 
Jun 2003
2×7×113 Posts 
Just to summarize then there is a 17% probability that 3 numbers in random have a common factor? Is it independent of the size of the numbers and factors?
Citrix 
20060201, 18:08  #18 
Sep 2002
100000110_{2} Posts 
I wonder what the probability would be if it were random pseudoprime?

20060204, 20:46  #19  
Jun 2005
2·191 Posts 
Quote:
If I may, I'd like to elaborate on how this is derived in simpler terms. It assumes you pick randomly from the infinite number of values available. I know very little about number theory or the Reimmann Zeta function, but I arrived at the same result using the following reasoning: For a given prime factor n, the odds of a randomly chosen number being divisible by n is 1/n. In order for 3 numbers to be mutually divisible by n, they must all satisfy this condition. (1/n)*(1/n)*(1/n) = 1/n^{3} So the odds of three numbers *not* being mutually divisible by 'n' is 11/n^{3}. If you can show this for all possible prime factors, then this is the probability of your 3 numbers having no common factor. Expanded, this looks like: (11/2^{3})*(11/3^{3})*(11/5^{3})*(11/7^{3})*(11/11^{3})... which converges to 0.8319... rather quickly. If you want to limit the domain of numbers to compare below a certain value, you only need to consider the primes below the chosen limit. For sufficiently large numbers, though, it really becomes insignificant, as the larger primes contribute very little to the probability. Drew Last fiddled with by drew on 20060204 at 20:57 

20060205, 01:18  #20 
Jun 2003
2·7·113 Posts 
Intersting approach.
But I kind of disagree. A huge number has more number of factors compared to a small number. Hence I think the formula should be log (a*b*C) *17% as the chances for this. Any thoughts? Citrix 
20060205, 02:09  #21  
Jun 2005
2·191 Posts 
Quote:
In any case, large numbers have a greater potential for having a factor, but the fact remains that they are most likely smaller factors. 3 arbitrarily chosen numbers are *extremely* unlikely to have a very large prime factor in common among them. For instance, the probability is 0.168085 that there's a common factor of or below 101 among 3 arbitrarily chosen numbers, but there's only another 0.000005 probability that they share a prime factor above 101, even if they're extraordinarily large numbers. Drew Last fiddled with by drew on 20060205 at 02:09 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
Combining low quality random numbers sources  only_human  Miscellaneous Math  3  20160520 05:47 
ECM on numbers with known factors  MatWurS530113  PrimeNet  15  20140425 04:51 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 
What is the proper way to benchmark 2 cores?  BlueCatZ1  Hardware  0  20060815 18:08 