Conference rusure::math

Well, the probability that two numbers are both divisible by 2 is
1/4.

The probability that two numbers are both divisible by 3 is 1/9.

The probability that two numbers are both divisible by 4 is 1/16.

etc.

So, the probability that two numbers are NOT relatively prime is

	1/4+1/9+1/16... = 1/(i^2) with i going from 2 to inf.

So, it looks like it's about PI/4 or somesuch (whatever that
sequence works out to)

/Eric

    Empirical results (100000 samples, integers <= 10E9) are about 55.4
    percent relative prime.
    

Hmm. 6/Pi^2 is about .608, so the estimate in .-1 does not agree with the
result in .-2. This may be explained by the fact that there are a LOT of 
very large numbers, and the larger a number the greater the chance that it 
has many divisors...

Actually the problem is not very clearly stated - how do you define a 
'random' sample from an unbounded population? Note that there is a very
high probability that the factorization of such numbers cannot be
determined within the lifetime of the universe.... 

In fact, now that I think about it, the probability is zero that, given two 
'random' integers, you can determine which is the larger of the two within
the lifetime of the universe. (I'll allow you one picosecond per digit.)

    Re .3:
    
    Dwayne:
    
    	Could you give us empirical results for integers <= 10E8, 10E7,
    etc., please?
    
    John

	.1 method counts pairs where both are divisible by 2*3 twice, etc.
The relative fraction of random pairs having exactly one common prime factor
is clearly
		sum 1/(p**2)        over all primes p

those having exactly two prime factors in common are 

		sum 1/(p*q)**2	    over all distinct primes p,q

etc, for 3, 4, ... prime factors; adding up these subtotals we must alternate
signs to keep the multiple-count accounting straight, and finally subtract
the whose mess from unity to get the probability of NO common prime factors.
The result is

	P = (1-(1/2)**2)*(1-(1/3)**2)*(1-(1/5)**2)* etc over the primes.

Invert both sides and use the fact that if abs(r) < 1, then 1/(1-r)=1+r+r**2...

	1/P = (1+(1/2**2)+(1/2**4)+...) * (1+(1/3**2)+...) * (1+ (1/5**2)...

in this product each term has  the form 1/n**2 ; uniqueness of prime factor-
ization says each such n turns up exactly once. So:

	1/P = sum(1/n**2),   n = 1,2,3,4,...all +ive numbers,

which is indeed ZETA(2) = (pi**2)/6; so P = 1/ZETA(2) = 6/(pi**2).
Reply .2 is numerically correct but it's 1/zeta(2), not zeta(2).

    Now that we know the correct answer, can someone provide a 
    correct statement of the problem?

      John

>> .0    What is the probability that two random positive integers are
>>       relatively prime?

>> .8    Now that we know the correct answer, can someone provide a 
>>       correct statement of the problem?

     One possible "correct statement" is:

     Let Prob(N, M) be defined by

                     The number of ordered pairs (i, j) where i and j
                     are relatively prime positive integers satisfying
                     1 <= i <= N and 1 <= j <= M
       Prob(N, M) = ---------------------------------------------------
                                      N * M

     Given this definition, the two parts of the problem are:

     1) Does the limit     LIM   Prob(N, N)   exist?
                         N -> oo

     2) If so, what is its value?

     I suppose that what we have shown so far is that *if* the limit
     exists, its value will be 6/(pi * pi), approximately 0.6079.

     *****************************************************************

     Possible variations would be to ask about

     3)   LIM      LIM    Prob(N, M)
         N -> oo  M -> oo

     4)   LIM      LIM    Prob(N, M)
         M -> oo  N -> oo

     Since Prob(N, M) = Prob(M, N), the limits in (3) and (4) either
     both fail to exist or both exist and have the same value.

     5) Do all three of these limits exist, and are they all equal?

     6) What about limits where M is a function of N, or N is a
        function of M?

                              Dan

|         Possible variations would be to ask about
|
|     3)   LIM      LIM    Prob(N, M)
|         N -> oo  M -> oo
    
    
    This doesn't sound useful, probably not what you meant.  Suppose
    
    	lim prob (n,m)    = 6/(pi^2)
        m->oo
    
    Then, you're asking for
    
    	lim 6/(pi^2)
        n->oo
    
    The last I heard, 6/(pi^2) varies immeasurably as n increases !
    
    /Eric

     Reply to .10

     In general, the fact that

           LIM    f(N, N)
          N -> oo

     exists does not necessarily imply that

           LIM      LIM    f(N, M)
          N -> oo  M -> oo
    
     exists.  Even if they both exist, the limits do not have
     to be equal.

     In this particular case, it can be shown that all the limits
     exist and are equal.  That's why I suggested it as a possible
     "correct statement" of the problem, as asked for in .8.

                              Dan

     I should have thought a little longer before my reply .11:

>> .10
>>    Suppose
>>    
>>    	lim prob (n,m)    = 6/(pi^2)
>>      m->oo

     But that's not the limit!

     If n = 1, the limit is 1.  If n = 2, the limit is 3/4.
     So even "in this particular case" the question is still interesting.

>> .11
>>     In this particular case, it can be shown that all the limits
>>     exist and are equal.

     By "all the limits" I meant (1), (3), and (4) in .9

                              Dan

         A proof is given in (the solution to) problem 10 of
         section 4.5.2 (page 337) of Knuth's volume 2,
         Seminumerical Algorithms, second edition.
    
         Problems 11-13 are related to this, too.
    
         Dan