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}$ ?

  • $\begingroup$ Size of the largest prime of $p$ is $p$ itself. Where $p$ is a prime.This is obvious, though. $\endgroup$ – Inceptio Apr 28 '13 at 14:50

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.

  • $\begingroup$ Very nice, thanks. $\endgroup$ – lhf Apr 29 '13 at 0:58

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.


enter image description here


  • $\begingroup$ I should have looked in Riesel. I had tried Pomerance but with not much luck. Thanks. $\endgroup$ – lhf Apr 29 '13 at 0:59

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.

  • $\begingroup$ Ah, I missed that when I searched. Thanks. $\endgroup$ – lhf Apr 29 '13 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.