mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-01-26, 16:35   #12
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Lightbulb Random numbers and proper factors.

Quote:
Originally Posted by John Renze
What does "two randomly chosen integers" mean? You can't put a uniform distribution on the entire set of integers, so there is some interpretation involved.

Specifically, you seem to be using the following heuristic: Let $n$ be an random integer and $p$ be a prime. Then $Pr(p | n) = 1/p$.

This is perfectly sensible and number theorists use this kind of reasoning all the time. I was wondering, though, how you formulate this precisely,.
I would advise you to visit a library and go thru the 2nd, volume of
"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
mfgoode is offline   Reply With Quote
Old 2006-01-26, 23:30   #13
John Renze
 
John Renze's Avatar
 
Nov 2005

24·3 Posts
Default

Quote:
Originally Posted by mfgoode
I would advise you to visit a library and go thru the 2nd, volume of
"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
That is not relevant to my question. Random number generators always pick a number in some range. Just the phrase, "a random integer" does not seem to have any meaning unless you specify a maximum. What appropriate probability measure on the set of integers could you use? So it seems to me that your original question is being implicitly reworded as:

"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
John Renze is offline   Reply With Quote
Old 2006-01-27, 02:43   #14
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

Quote:
Originally Posted by John Renze
That is not relevant to my question. Random number generators always pick a number in some range. Just the phrase, "a random integer" does not seem to have any meaning unless you specify a maximum. What appropriate probability measure on the set of integers could you use? So it seems to me that your original question is being implicitly reworded as:

"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
http://mathworld.wolfram.com/RelativelyPrime.html

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 2006-01-27 at 02:45
Orgasmic Troll is offline   Reply With Quote
Old 2006-01-27, 03:50   #15
John Renze
 
John Renze's Avatar
 
Nov 2005

24·3 Posts
Default

Quote:
Originally Posted by TravisT
Thank you.
John Renze is offline   Reply With Quote
Old 2006-01-28, 10:33   #16
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Thumbs up Random numbers and proper factors.

Quote:
Originally Posted by akruppa
I suppose the analysis will be similar to that for two randomly chosen integers. We had that one before in this forum. The result for two random integers was 1/zeta(2), the results for 3 random integers should be 1/zeta(3) which matches your constant.
Alex
You are absolutely right akruppa.
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
mfgoode is offline   Reply With Quote
Old 2006-02-01, 02:48   #17
Citrix
 
Citrix's Avatar
 
Jun 2003

23×197 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-02-01, 18:08   #18
jocelynl
 
Sep 2002

26210 Posts
Default

I wonder what the probability would be if it were random pseudoprime?
jocelynl is offline   Reply With Quote
Old 2006-02-04, 20:46   #19
drew
 
drew's Avatar
 
Jun 2005

2·191 Posts
Default

Quote:
Originally Posted by Citrix
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?
That's correct.

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/n3

So the odds of three numbers *not* being mutually divisible by 'n' is 1-1/n3. If you can show this for all possible prime factors, then this is the probability of your 3 numbers having no common factor.

\large \prod_{n=1}^\infty 1-\frac{1}{p(n)^3}

Expanded, this looks like:

(1-1/23)*(1-1/33)*(1-1/53)*(1-1/73)*(1-1/113)...

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 2006-02-04 at 20:57
drew is offline   Reply With Quote
Old 2006-02-05, 01:18   #20
Citrix
 
Citrix's Avatar
 
Jun 2003

23×197 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-02-05, 02:09   #21
drew
 
drew's Avatar
 
Jun 2005

1011111102 Posts
Default

Quote:
Originally Posted by Citrix
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
This isn't something to disagree over...it's a matter of fact, not opinion.

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 2006-02-05 at 02:09
drew is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
Combining low quality random numbers sources only_human Miscellaneous Math 3 2016-05-20 05:47
ECM on numbers with known factors MatWur-S530113 PrimeNet 15 2014-04-25 04:51
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56
What is the proper way to benchmark 2 cores? BlueCatZ1 Hardware 0 2006-08-15 18:08

All times are UTC. The time now is 00:06.

Sat Dec 5 00:06:20 UTC 2020 up 1 day, 20:17, 0 users, load averages: 1.78, 1.77, 1.65

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.