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.
Posting my first Math-StackExchange answer...
According to this section of Wikipedia, due to Dixon's theorem, the probability of largest prime factor of $n$ to be less than $n^{1/m}$ is approximately $m^{-m}$ for any real $m \ge 1$.
So probability of largest prime factor to be less than $\sqrt n = n^{1/2}$ is approximately $2^{-2} = 1/4 = 0.25$. To be less than $\sqrt[3]n = n^{1/3}$ is approximately $3^{-3} = 1/27 \approx 0.037$.
I don't know the details of this theorem, I just found this quotation in Wikipedia and thought it might be useful for you. Also I don't know how approximate is this formula.
I tried to check this formula experimentally and wrote Python code for that (using Pollard-Rho and Fermat algorithms). Don't know if according to rules it is allowed to post code here on Math-StackExchange, so providing just links:
You can see (run) my code in action here (and here is a copy of my code just in case if first link is broken, second link is not runnable).
Results for 10K checked 64-bit numbers here:
Checked nums: 10242
Expected: 1.0: 1.00000, 1.5: 0.54433, 2.0: 0.25000, 2.5: 0.10119, 3.0: 0.03704, 3.5: 0.01247, 4.0: 0.00391, 4.5: 0.00115, 5.0: 0.00032, 5.5: 0.00008
Actual: 1.0: 1.00000, 1.5: 0.51541, 2.0: 0.23203, 2.5: 0.09008, 3.0: 0.03202, 3.5: 0.01021, 4.0: 0.00321, 4.5: 0.00105, 5.0: 0.00038, 5.5: 0.00005
Here are pairs of m (from formula above) and probability. So Expected (by formula above) is close to Actual (experimental with factoring of 64-bit numbers), especially close for larger m. Maybe formula is more precise for larger than 64-bit numbers that I checked or for more amount of tested numbers.
