# Average smallest prime factors

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?

• The definition is $$\operatorname{ASPF}(n) = \frac{1}{n-1} \sum_{k = 2}^n \operatorname{SPF}(k)\,?$$ Jun 25, 2015 at 11:32
• Correct, I added it in the question. Jun 25, 2015 at 11:39
• The sums are tabulated at oeis.org/A088821 but with no further information. Jun 25, 2015 at 12:51

## 1 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.$$

• Sorry for the late comment, but where does the $\frac 12$ come from between $n\pi(n)$ and $\frac{n^2}{2\log n}$?
– Avi
Nov 10, 2015 at 16:03
• We have $$\sum_{k = 2}^{n-1} \pi(k) \sim \frac{n^2}{2\log n},$$ so if we subtract that from $n \pi(n) \sim \frac{n^2}{\log n}$, the leading term is $\frac{n^2}{2\log n}$. Nov 10, 2015 at 16:13
• What I start wondering about is: how did my (really) uneducated guess agree so good with the result of this elaborate calculation? Dec 8, 2015 at 12:26
• @HansStricker It might have been sheer coincidence, but I consider it more likely that your guess wasn't as uneducated as you think. One does tend to have more experience than one is consciously aware of. Dec 8, 2015 at 12:33