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$ – Daniel Fischer Jun 25 '15 at 11:32
  • $\begingroup$ Correct, I added it in the question. $\endgroup$ – Hans-Peter Stricker Jun 25 '15 at 11:39
  • $\begingroup$ The sums are tabulated at oeis.org/A088821 but with no further information. $\endgroup$ – Gerry Myerson Jun 25 '15 at 12:51

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$ – Laertes Nov 10 '15 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$ – Daniel Fischer Nov 10 '15 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$ – Hans-Peter Stricker Dec 8 '15 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$ – Daniel Fischer Dec 8 '15 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.