Probability that a Random Integer...

Date: 7/18/96 at 2:42:49
From: don mcmahon&sheri anderson
Subject: Probability that a Random Integer...

I started trying to figure out what the probability that an integer 
chosen randomly would be an integer multiple of a given integer "n"
(or perhaps of a prime "p")...and then the probability that it would 
be a multiple of, say, the integers 2...7, and so on. I think I got 
stuck on trying to figure out how to formulate  the "or" probabilities 
and add things up properly. I think my idea was to generate a sequence 
P(n) where P(n) would be the probability a random integer would be a 
multiple of at least one of the integers from 2 up to n. I think I got 
tangled up in the lattice of integers and then had to go settle a 
civil war in the sandbox in the backyard. Can you head me in the 
right direction?

Sheri Anderson

Date: 7/18/96 at 19:58:55
From: Doctor Tom
Subject: Re: Probability that Random Integer...

Well, to be precise (and that's what we mathematicians have to be!),
I have to know exactly what you mean by "an integer chosen randomly".

If you're talking about the entire infinite set of integers, there is
no way to do this without some sort of a distribution function over
the integers, and there is no such function that gives an "equal
probability" for all integers.

To make things precise, here's what I'll assume you mean:  If M is
a very large integer, and we randomly (with equal probability)
choose an integer between 0 and M, what's the probability that it
is divisible by n?  For any fixed M, you can work this out, and then
if we take the limit of these probabilities as M goes to infinity,
I think that will be what you want.

So if your question just concerns a single number n, the answer is
that the limiting probability is 1/n.  For large M, roughly 1/n of
the integers less than M are divisible by n, and the error is smaller
and smaller as M gets larger and larger.

If you ask, "What's the probability that a number is divisible by
n and m?", I think you begin to see the problem - for example, if
n = 2 and m = 4, it's 1/4, since anything divisible by 4 is
automatically divisible by 2.

If you ask the general question, "What's the probability that a number 
is divisible by all of the numbers n1, n2, n3, ..., nx?" the answer is 
"if z = the least common multiple of n1, n2, ..., nx, then the 
probability is 1/z".

The least common multiple of a set of integers is the smallest integer
that all of them divide.  For example, the least common multiple
of 4 and 6 is 12.  Of 7 and 11 is 77.  And so on.

To find the least common multiple of a set of numbers, factor all of 
them into prime factors.  For each prime that appears anywhere in the 
list, find the number in which the highest power of that prime 
appears, and include that power of the prime in a product.

The grand product is the LCM (least common multiple).

For example, to find the LCM of 24, 125, 32, 100, and 444, where
"*" indicates multiplication, and "^" exponentiation:

24 = 2^3*3^1
125 = 5^3
32 = 2^5
100 = 2^2*5^2
444 = 2^2*3^1*37^1

LCM = 2^5*3^1*5^3*37^1

I hope it's obvious why this works, and I won't bother to multiply
out the number in my example.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/