Probability for composite $n$ to have prime factor $\geq \sqrt n$

83 Views Asked by At

Let $\operatorname{GPF}(n)$ denote the largest prime factor of $n\in\mathbb N_{>1}$. My computer tests for intervalls $[m,n]$, where $n<10,000,000$, suggests that the probability $\operatorname{P}(\operatorname{GPF}(n)\geq\sqrt n)$ is asymptotically equivalent with a constant $\approx\frac{8}{11}$.

Can this be proved, heuristically understood or falsified?

1

There are 1 best solutions below

0
On

Begin by noting that if a natural $n$ has a prime factor $p \geq \sqrt{n}$, then clearly $p$ is unique for $n$. So let's fix some prime $p$ and consider all naturals for which $p$ satisfies this property. Clearly, these are just all naturals of the form $ap$, where $a\in \Bbb N, a \leq p$. From this, we get that if we fix some natural $N$, then the number of naturals less than $N$ satisfying this property is precisely $$\sum_{p \in \Bbb P, p \leq \sqrt{N}}p + \sum_{p \in \Bbb P, \sqrt{N} < p \leq N}\lfloor \frac np \rfloor$$ where $\Bbb P$ is of course the set of primes.