22
$\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$
1
  • $\begingroup$ Size of the largest prime of $p$ is $p$ itself. Where $p$ is a prime.This is obvious, though. $\endgroup$
    – Inceptio
    Apr 28, 2013 at 14:50

4 Answers 4

14
$\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.

$\endgroup$
4
  • $\begingroup$ Very nice, thanks. $\endgroup$
    – lhf
    Apr 29, 2013 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$
    – Dabed
    Mar 14, 2020 at 16:57
  • 1
    $\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, 2020 at 17:12
  • $\begingroup$ Thanks again that was useful $\endgroup$
    – Dabed
    Mar 22, 2020 at 0:02
9
$\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

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

$\endgroup$
1
  • $\begingroup$ I should have looked in Riesel. I had tried Pomerance but with not much luck. Thanks. $\endgroup$
    – lhf
    Apr 29, 2013 at 0:59
4
$\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.

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .