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$ Commented Aug 13, 2021 at 12:28
  • 1
    $\begingroup$ What is the context for asking this question? It seems like a very random function. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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
    Commented Aug 14, 2021 at 13:00

You must log in to answer this question.

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