Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
It is well known and easy to prove that the smallest prime factor of an integer $n$ is at most equal to $\sqrt n$. What can be said about the largest prime factor of $n$, denoted by $P_1(n)$? In particular:
What is the probability that $P_1(n)>\sqrt n$ ?
More generally, what is the expected value of the size of $P_1(n)$, measured by $\frac{\log P_1(n)}{\log n}$ ?
Take the negation and this is a very well-known question: what is the probability that all prime factors of $n$ are $\le \sqrt{n}$? The answer is known quite generally: for any real $u\ge 1$, the probability that the prime factors of $n$ are $\le n^{1/u}$ is given by the Dickman–de Bruijn rho function, defined by a delay-differential equation. For $u=2$ we have $\rho(u) = 1-\log 2$, as in Ross Millikan's answer, but there is a very easy calculation that gives this particular case:
$$\#\{n \le x: P_1(n) > \sqrt{n}\} = \sum_{p} \#\{n \le x, n < p^2: p \mid n\} = \sum_{p\le \sqrt{x}} (p-1) + \sum_{p > \sqrt{x}} \lfloor x/p \rfloor \\ = x \log 2 + O(x/\log x),$$
where the main term comes from Mertens' theorem on $\sum_p {1/p}$ and the error terms can be deduced from the Prime Number Theorem (or Chebyshev's upper bound on $\pi(x)$).
Here, by convention, $p$ is assumed to only take prime values. The reason this is so simple is that no $n$ here can have more than one prime factor $> \sqrt{n}$.
The answer to your second question is known as the Golomb-Dickman constant. Wikipedia gives it as about $0.62433$, but I doubt anything is known about its rationality, say.
In Hans Riesel, Prime Numbers and Computer Methods for Factorization, he gives a few approaches to largest and second largest prime factor. On pages 157-158, he gives a heuristic for a "typical" factorization, that suggests the largest gives $$ \log P_1 / \log n \approx 1 - 1/e \approx 0.6321, $$ $$ \log P_2 / \log n \approx (1 - 1/e) / e \approx 0.2325. $$ On page 161 he mentions that Knuth and Trabb-Pardo get $0.624, \; \; 0.210$ with a more rigorous argument. This is 1976, Theoretical Computer Science, volume 3, pages 321-348. Analysis of a Simple Factorization Algorithm. So I would say you want to get a copy of Knuth and Trabb-Pardo, which is reproduced, with later comments, in KNUTH
He then presents the Erdos-Kac theorem on pages 158-159, finally giving probability distribution curves for the three largest prime factors on page 163. These graphs would be what I call "cumulative distribution functions," being the integral of the "probability distribution function." These are also taken from Knuth and Trabb -Pardo. Let me make a jpeg.
KNOTE: The table on page 163 of $\rho_1(\alpha)$ agrees exactly with the table of $\rho(u)$ in Erick's link on the Dickman-de Bruijn function. So, I think you have a winner.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
In Mathworld it states that the probability that $P_1(n) \gt \sqrt n$ is $\log 2$. The first few rough numbers are given in OEIS A064052 but there are no references.
