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?

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

1 Answer 1


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},$$


$$\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.$$

  • $\begingroup$ Sorry for the late comment, but where does the $\frac 12$ come from between $n\pi(n)$ and $\frac{n^2}{2\log n}$? $\endgroup$
    – Avi
    Nov 10, 2015 at 16:03
  • 1
    $\begingroup$ 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}$. $\endgroup$ Nov 10, 2015 at 16:13
  • $\begingroup$ What I start wondering about is: how did my (really) uneducated guess agree so good with the result of this elaborate calculation? $\endgroup$ Dec 8, 2015 at 12:26
  • $\begingroup$ @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. $\endgroup$ Dec 8, 2015 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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