Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $f(p_1^{a_1}...p_k^{a_k})=a_1$ where $p_1<...<p_k$ 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)]$.
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<...<p_k<p\\p_1...p_k|n}}(-1)^k=\begin{cases}1&\mbox{if $p$ is the smallest prime factor of $n$}\\0&\mbox{otherwise}\end{cases}.$$ 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<...<p_k<p\\p_1...p_k|x}}(-1)^k.$$ Using $v_p(x)-1=\sum_a1$ for $a\geq2$ with $p^a|x$, we get $$\widehat{g}(n)=\sum_{p_1<...<p_k<p}(-1)^k\sum_{a\geq2}\left\lfloor\frac{n}{p_1...p_kp^a}\right\rfloor.$$ 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<p}\frac1{p_1...p_kp}.$$ With the fundamental theorem of arithmetic, we can rewrite this as $$\widehat{S}=\sum_p\frac1{p(p-1)}\prod_{q<p}\left(1+q^{-1}\right).$$ Using $1+x\leq e^x$ we get $$\widehat{S}\leq\sum_p\frac1{p(p-1)}\exp\left(\sum_{q<p}\frac1q\right).$$ Since $\sum_{q<p}q^{-1}-\log\log p$ converges, we can bound $\sum_{q<p}q^{-1}\leq\log\log p+C$ 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<p}\left(1-q^{-1}\right).$$ 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.
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.$$
