|
I suspect that this is an extraordinarily difficult function to find.
Here's a microstep in what may be the right direction:
Problem: for large p, p prime, what is the probability that a random integer
N (ignoring the difficulty of picking random integers) is divisible by p but
by no smaller prime?
To approximate this answer, look at the interval [0,p!).
The pattern of the numbers we are looking for in this interval will be
repeated in [p!,2*p!), [2*p!,3*p!), etc, so the density of such numbers
in this interval (number of occurrences divided by p!) is the probability
we seek.
The numbers which are divisible by p but by no smaller prime are:
p, p*p1, p*p2, ... where p1, p2, etc are the 1st, 2d,
p^2, p^2*p1, p^2*p2, ... etc. primes > p
p^3, p^3*p1, p^3*p2, ...
How many numbers are enumerated here? Consider the first line of the
enumeration. If p*x is less than p! then x must be less than p!/p;
but we must exclude all x between 2 and p inclusive, and all non-prime x.
Let pi(n) be the number of primes < n. Then the number of entries on the
first line of the enumeration is pi(p!/p)-pi(p).
Similiarly, the number of entries on the second line is pi(p!/p^2)-pi(p), etc.
There are [ln(p!)/ln(p)] lines in the enumeration, and the last line is
a special case, having exactly one element.
Since p is large, there are some approximations that can be used to simplify
things:
pi(n) = n/ln(n) (some famous theorem or other;
there may be a constant of
proportionality involved)
ln(p!) = p*ln(p)-p+ln(2*pi*p)/2 (Stirling's formula - pi here
is the usual 3.14159...)
I didn't have the heart to expand the entire enumeration and divide by
p! to get the probability; however, by ruthlessly throwing away the less
significant terms (i.e. everything but pi(p!/p) in the enumeration, and
the last term in Stirling's formula) I came up with an approximate
probability of:
1
-------------------------
p * (p-1) * (ln(p-1) - 1)
Good luck in verifying it empirically for any given large p.....
|