3
$\begingroup$

Let $P\subseteq \mathbb{N}$ be the set of primes, and for any integer $n>1$ let $L(n) = \max\{p \in P: p \mid n\}$ be the largest prime divisor of $n$. Moreover, for $n \in \mathbb{N}$ with $n>1$ we let $M(n)$ to be the median of the set $$\{L(m)/m : m\in \mathbb{N} \land 1 < m \leq n\}.$$

Does $\lim_{n\to\infty}M(n)$ exist? If yes, is its value known?

$\endgroup$
10
  • 3
    $\begingroup$ The number of distinct prime divisors of $n$ grows on average as $\log \log n$. This should give you that $\lim_{n \to \infty} M(n) = 0$. $\endgroup$ Aug 13, 2021 at 12:28
  • 1
    $\begingroup$ What is the context for asking this question? It seems like a very random function. $\endgroup$ Aug 13, 2021 at 12:33
  • 1
    $\begingroup$ suffices to show average is $0$. Can upper bound average by $\frac{1}{n}\sum_{2 \le m \le n} \frac{1}{m}\sum_{p \mid m} p = \frac{1}{n} \sum_p p \sum_{2 \le m \le n \\ p \mid m} \frac{1}{m} = \frac{1}{n}\sum_p p\sum_{1 \le k \le n/p} \frac{1}{pk} \le \frac{1}{n} \sum_{1 \le k \le n} \frac{1}{k} C\frac{n}{\log(n/k)} \le 2C/\log n$. So all we needed really was that primes have $0$ density (which is also necessary for the median/mean to be $0$). $\endgroup$ Aug 13, 2021 at 14:13
  • 1
    $\begingroup$ Thanks for your comments. Please post one as an answer so we can close this thread. @Carl-FredrikNybergBrodda - the context was a silly one: I saw a car with a license plate "AB 639" and noticed that $639 = 3 \cdot 3 \cdot 71$ where 71 is much higher than the square root of 639. So I was wondering how "common" this phenomenon was and tried to put this hand-wavy question into some solid-ish mathematics. $\endgroup$ Aug 13, 2021 at 20:06
  • 1
    $\begingroup$ @DominicvanderZypen You might be interested in the following result. Writing $L(n) = n^{\alpha(n)}$, the random variable $\alpha \in [0,1]$ has a continuous limiting distribution if $n$ is randomly sampled from $[1,x]\cap \mathbb{Z}$ and $x \to \infty$. $\endgroup$ Aug 14, 2021 at 13:16

1 Answer 1

3
$\begingroup$

The number of prime divisors of $n$ grows typically as $\log \log n$. Suppose $n$ has $k$ prime factors. Now $n/L(n)$ has only $k-1$ prime factors, so $$ k-1 \approx \log \log \frac{n}{L(n)} = \log \log n + \log\left( 1-\frac{\log L(n)}{\log n}\right) = k + \log\left( 1-\frac{\log L(n)}{\log n}\right) $$ and hence $$ \log\left( 1-\frac{\log L(n)}{\log n}\right) \approx -1 $$ i.e., typically we will have $$ \log L(n) \approx \left( 1-\frac{1}{e}\right)\log n $$ or indeed $$ L(n) \approx n^{1-\frac{1}{e}} = n^{0.632...}. $$ Note that this means that typically the largest prime divisor of $n$ will be bigger than $\sqrt{n}$, which is a nice isolated statement as well.

As mathworker21 noted, it suffices to show that the average of $L(m)$ for $1 < m \leq n$ tends to $0$ as $n \to \infty$. Let $A(n)$ be this average. Thus in the typical case $$ A(n) = \frac{1}{n} \sum_{m=1}^n \frac{L(m)}{m} \approx \frac{1}{n} \sum_{m=1}^n \frac{1}{m^{\frac{1}{e}}} = \frac{1}{n} H_{n,\frac{1}{e}} $$ where $H_{n,\frac{1}{e}}$ is the $n$th generalized harmonic number of order $\frac{1}{e}$. As $n\to \infty$, an asymptotic expansion of this right-hand side yields $$ A(n) \approx \frac{1}{n} H_{n,\frac{1}{e}} = \frac{e}{n^{1/e}(e-1)} + \frac{\zeta(\frac{1}{e})}{n} + O\left( \frac{1}{n^2}\right) \to 0 $$ as $n \to \infty$. Hence also $\lim_{n \to \infty} M(n) = 0$.

$\endgroup$
1
  • 2
    $\begingroup$ In the first line, how are you getting that $k-1$ is about $\log \log \frac{n}{L(n)}$? That would be true if numbers of the form $\frac{n}{L(n)}$ look typical, but that isn't obvious. $\endgroup$
    – JoshuaZ
    Aug 14, 2021 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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