17
$\begingroup$

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

$\endgroup$
  • $\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
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, thanks. $\endgroup$ – lhf Apr 29 '13 at 0:58
  • $\begingroup$ Is there something you could suggest to further read about it?, it feels trivial but I get lost as to why it looks like $\sum_{p\le \sqrt{x}} (p-1) + \sum_{p > \sqrt{x}} \lfloor x/p \rfloor$ and either how Mertens/PNT give the estimates, thanks. $\endgroup$ – Daniel D. Mar 14 at 16:57
  • $\begingroup$ @DanielD. If $p \le \sqrt{x}$ then the $n < p^2$ condition dominates and there are exactly $p-1$ multiples of $p$ up to (not including) $p^2$. If $p > \sqrt{x}$ then the $n \le x$ condition dominates and the summand counts multiples of $p$ up to $x$. $\endgroup$ – Erick Wong Mar 14 at 17:12
  • $\begingroup$ Thanks again that was useful $\endgroup$ – Daniel D. Mar 22 at 0:02
7
$\begingroup$

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

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

| cite | improve this answer | |
$\endgroup$
  • $\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
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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.