21
$\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

12
$\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
  • $\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$

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.