Average smallest prime factors

832 Views Asked by At

I looked at the average smallest prime factor (ASPF) for the numbers up to N:

$\text{ASPF}(N) = \frac{1}{N-1}\ \Sigma_{k=2}^N \text{SPF}(k)$

ASPF(100) = 13

ASPF(1,000) = 79

ASPR(10,000) = 578

ASPF(100,000) = 4552

ASPF(1,000,000) = 37568

(The SPF of a prime number is supposed to be itself.)

The resp. growth factors are 6.1, 7.3, 7.8, 8.2

What can be said about the limit L of these growth factors? Is there one, i.e. ASPF(10 * N) = L * ASPF(N) for large N?

1

There are 1 best solutions below

4
On BEST ANSWER

Asymptotically, only the primes matter. If $p$ is the smallest prime factor of a composite $k$, then $k \geqslant p^2$, and so the contribution of composites to the average can be estimated from above by $\sqrt{n}$ via

$$\sum_{p \leqslant \sqrt{x}} \bigg\lfloor\frac{n}{p}\biggr\rfloor\cdot p \leqslant \sum_{k = 2}^{\lfloor\sqrt{n}\rfloor} \biggl\lfloor\frac{n}{k}\biggr\rfloor\cdot k \leqslant n(\sqrt{n}-1) \leqslant (n-1)\sqrt{n}.$$

The contribution of the primes, ignoring any composites, is obtained via

\begin{align} \sum_{p \leqslant n} p &= \sum_{k = 2}^n k\cdot (\pi(k) - \pi(k-1))\\ &= \sum_{k = 2}^n k\pi(k) - \sum_{m = 1}^{n-1} (m+1)\pi(m)\\ &= n\pi(n) - \sum_{k = 2}^{n-1} \pi(k)\\ &= \frac{n^2}{2\log n} + O\biggl(\frac{n^2}{(\log n)^2}\biggr), \end{align}

which shows that the contribution of the primes to the average smallest prime factor is

$$\frac{n}{2\log n} + O\biggl(\frac{n}{(\log n)^2}\biggr).$$

Hence asymtotically

$$\operatorname{ASPF}(n) \sim \frac{n}{2\log n},$$

and

$$\frac{\operatorname{ASPF}(10 n)}{\operatorname{ASPF}(n)} \sim \frac{10 n}{2(\log n + \log 10)}\cdot \frac{2\log n}{n} = \frac{10}{1+\frac{\log 10}{\log n}} \to 10.$$