Does the sum of the power of the smallest prime factor grow linearly?

Let $$f(p_1^{a_1}...p_k^{a_k})=a_1$$ where $$p_1<... and let $$g(n)=\sum_{k<=n}f(k)$$. Then is $$g(n)=\mathcal{O}(n)$$?

I know that for $$f(p_1^{a_1}...p_k^{a_k})=k$$ we would have gotten $$g(n)=\Theta(n\log\log n)$$, which follows from the fact that $$\sum_{p<=n}\frac1p=\Theta(\log\log n)$$ where $$p$$ must be prime. However, I intuitively expect $$f(p_1^{a_1}...p_k^{a_k})=a_1$$ to be smaller on average.

If you're able to, I would also love to know if $$g(n)/n$$ converges to any specific value.

Let $$h(n) = \sup_{p^e | n} e$$. Any integer decomposes uniquely as $$nm^2$$ with $$n$$ square-free. Also $$h(m) \le 2\log m$$ thus

$$\sum_{n \le x} f(n) \le \sum_{n \le x} h(n)= \sum_{m \le x^{1/2}} \sum_{n \le x/m^2, |\mu(n)|=1} h(m^2 n)$$ $$\le \sum_{n \le x} |\mu(n)| + \sum_{2 \le m \le x^{1/2}} (2 h(m)+1)\sum_{n \le x/m^2} |\mu(n)| \le x(1+ \sum_{2 \le m \le x^{1/2}} \frac{4\log(m)+1}{m^2})$$ $$\le x(1+\zeta(2)-4\zeta'(2))$$

For a similar reason $$\lim_{x \to \infty} \frac{\sum_{n \le x}f(n)}{x}$$ converges to a non-zero value $$\in [\frac{1}{\zeta(2)},1+\zeta(2)-4\zeta'(2)]$$.

• I think I understand the point and I like the square-free decomposition, but the details are confusing to me. So for $c=(\log2)^{-1}\approx1.44$ we have $h(m)\leq c\log m$. We also have $h(m^2n)\leq 2h(m)+h(n)=2h(m)+1$. Then $$\sum_{n\leq x}h(n)=\sum_{m\leq x^{1/2}}\sum_{n\leq x/m^2}|\mu(n)|h(m^2n)\leq\sum_{m\leq x^{1/2}}(2h(m)+1)\sum_{n\leq x/m^2}|\mu(n)|\leq x\sum_{m\leq x^{1/2}}\frac{2c\log m+1}{m^2}.$$ This is the idea right? Commented Aug 18, 2019 at 16:30
• sure plus that $h(m^2n)=2h(m)$ when $|\mu(n)|=1$ Commented Aug 18, 2019 at 16:33
• {}{}{}{}{}{}{}{}{}{} Commented Aug 18, 2019 at 16:34
• But for $n=m=2$ we have $h(m^2n)=3\neq 2=2h(m)$ and $|\mu(n)|=1$? Commented Aug 18, 2019 at 16:37
• hmm right I need to replace $4$ by $6$ tks Commented Aug 18, 2019 at 16:39

Theorem

Let $$u(n)$$ be the largest prime factor of $$n$$. The following is a proof that $$S:=\sum_{x\geq2}\frac{-\mu(x)}{x(u(x)-1)}$$ converges, and $$g(n)/n\to S+1$$ as $$n\to\infty$$.

Basic manipulations

Consider $$\widehat{f}(n):=f(n)-1$$ and $$\widehat{g}(n):=\sum_{2\leq k\leq n}\widehat{f}(k)=g(n)-n+1$$. We do some basic manipulations on $$\widehat{f}$$ and $$\widehat{g}$$. By inclusion-exclusion, for any number $$n$$ with a prime factor $$p$$ we have $$\sum_{\substack{p_1<... Let $$v_p(n)$$ be the $$p$$-adic valuation of $$n$$, so the largest $$k$$ such that $$p^k|n$$. We get $$\widehat{g}(n)=\sum_{x=2}^n\sum_{p|x}\left(v_p(x)-1\right)\sum_{\substack{p_1<... Using $$v_p(x)-1=\sum_a1$$ for $$a\geq2$$ with $$p^a|x$$, we get $$\widehat{g}(n)=\sum_{p_1<... Substituting $$x=p_1...p_kp$$ and $$b=a-1$$ we get $$\widehat{g}(n)=\sum_{x\geq2}-\mu(x)\sum_{b\geq1}\left\lfloor\frac{n}{xu(x)^b}\right\rfloor.$$ So finally we can write $$\frac{\widehat{g}(n)}n=\sum_{x\geq2}\sum_{b\geq1}\frac{-\mu(x)}n\left\lfloor\frac{n}{xu(x)^b}\right\rfloor.$$ We can now move on to investigating the limiting behaviour.

Infinite series

This gives us motivation to look at the infinite series $$S=\sum_{x\geq2}\sum_{b\geq1}\frac{-\mu(x)}{xu(x)^b}.$$ Note that the sum over $$b$$ is a geometric series, so we can rewrite $$S=\sum_{x\geq2}\frac{-\mu(x)}{x(u(x)-1)}.$$ We show that the series is absolutely convergent, i.e., that the series $$\widehat{S}:=\sum_{x\geq2}\frac{|\mu(x)|}{x\left(u(x)-1\right)}$$ converges. We substitute $$p=u(x)$$ and sum over the primes $$p$$ first and then all $$x\geq2$$ with $$|\mu(x)|=1$$ and $$u(x)=p$$. We get $$\widehat{S}=\sum_p\frac1{p-1}\sum_{p_1<...p_k With the fundamental theorem of arithmetic, we can rewrite this as $$\widehat{S}=\sum_p\frac1{p(p-1)}\prod_{q Using $$1+x\leq e^x$$ we get $$\widehat{S}\leq\sum_p\frac1{p(p-1)}\exp\left(\sum_{q Since $$\sum_{q converges, we can bound $$\sum_{q for some constant $$C$$ to get $$\widehat{S}\leq e^C\sum_p\frac{\log p}{p(p-1)}.$$ That this series converges, even when summing over all positive integers $$p$$ instead of only the primes, can be seen with an integral test.

Conclusion

We view $$\widehat{g}(n)/n$$ as an infinite series. Every term converges to the corresponding term in $$S$$, while they are also absolutely bounded by the absolute value of that term in $$S$$. Since $$S$$ is absolutely convergent, we can conclude from this that $$\widehat{g}(n)/n\to S$$ as $$n\to\infty$$. Since $$g(n)=\widehat{g}(n)+n-1$$, it follows that $$g(n)/n\to S+1$$ as $$n\to\infty$$.

Remarks

Using the same techniques as with $$\widehat{S}$$ and the fact that $$S$$ converges absolutely, we can rewrite $$S=\sum_p\frac1{p(p-1)}\prod_{q This appears to make the series converge faster. Calculating the sum over the primes $$p\leq10^8$$ gives $$\lim_{n\to\infty}\frac{g(n)}n\approx1.6125177915.$$ I can also calculate the sum over the primes $$p\leq10^{10}$$ pretty fast. The aforementioned digits stay the same, but the double-precision floating-point format is not precise enough to give many more digits. Worth mentioning is that calculating the actual value $$g(n)/n$$ for large $$n$$ indeed seems to approach this value.

• Just finished reading. Very nice! (and pleasant to read). There was one $n$ that should have been an $x$ that I fixed. The final form $\sum_p \frac{1}{p(p-1)}\prod_{q < p} (1-q^{-1})$ is indeed very clean. Commented Jan 29, 2021 at 7:05

Yes. By inclusion-exclusion, $$\sum_{k \le n} f(k) = \sum_{\substack{p_1 < \dots < p_r \\ p_1\dots p_r \le n}} (-1)^{r+1}\sum_{\substack{k \le n \\ p_1\dots p_r | k}} v_{p_r(k)} = \sum_{\substack{p_1 < \dots < p_r \\ p_1\dots p_r \le n}} (-1)^{r+1} \sum_{j=1}^{n/(p_1\dots p_r)} \sum_{a \ge 1} 1_{p_r^a \mid p_1\dots p_r j} = \sum_{\substack{p_1 < \dots < p_r \\ p_1\dots p_r \le n}} (-1)^{r+1} \sum_{a \ge 1} \sum_{j=1}^{n/(p_1\dots p_r)} 1_{p_r^{a-1} \mid j} = \sum_{\substack{p_1 < \dots < p_r \\ p_1\dots p_r \le n}} (-1)^{r+1} \sum_{a \ge 1} \lfloor \frac{n}{p_1\dots p_{r-1} p_r^a} \rfloor.$$

• I don't follow your first formula. You want to count $\sum_{k \le n, f(k) = m} 1$ right ? It is $\sum_{p \le n} \sum_{ n\le k/p^m, \gcd(n,\prod_{q \le p} q)=1} 1 = \sum_{p \le n} \sum_{d | \prod_{q \le p} q} \mu(d) \lfloor \frac{k/p^m}{d} \rfloor$ Commented Aug 18, 2019 at 16:47
• We sum $v_2(k)$ over even $k \le n$. We then sum $v_3(k)$ over $3 \mid k \le n$, but we have to subtract the sum of $v_3(k)$ over $6 \mid k \le n$. Etc. Commented Aug 18, 2019 at 16:49
• What is $v_a(b)$? Commented Aug 18, 2019 at 16:55
• @SmileyCraft maximum power of $a$ dividing $b$, i.e. $\sum_{j \ge 1} 1_{a^j \mid b}$. It is quite standard. Commented Aug 18, 2019 at 16:56
• I just checked for $x$ up to $10^7$ and the sum is $1.6124175$. When I calculate $\frac1n\sum_{k\leq n}f(k)$ for $n=10^7$ I get $1.6125084$. So to me it seems like we have a winner. Somewhat ironically, though, this sum seems to converge at a slower rate than the original sum. Commented Aug 18, 2019 at 17:46