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.


3 Answers 3


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)]$.

  • $\begingroup$ 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? $\endgroup$ Commented Aug 18, 2019 at 16:30
  • $\begingroup$ sure plus that $h(m^2n)=2h(m)$ when $|\mu(n)|=1$ $\endgroup$
    – reuns
    Commented Aug 18, 2019 at 16:33
  • 2
    $\begingroup$ {}{}{}{}{}{}{}{}{}{} $\endgroup$
    – reuns
    Commented Aug 18, 2019 at 16:34
  • $\begingroup$ But for $n=m=2$ we have $h(m^2n)=3\neq 2=2h(m)$ and $|\mu(n)|=1$? $\endgroup$ Commented Aug 18, 2019 at 16:37
  • $\begingroup$ hmm right I need to replace $4$ by $6$ tks $\endgroup$
    – reuns
    Commented Aug 18, 2019 at 16:39


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.


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


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.

  • $\begingroup$ 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. $\endgroup$ 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.$$

  • $\begingroup$ 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$ $\endgroup$
    – reuns
    Commented Aug 18, 2019 at 16:47
  • $\begingroup$ 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. $\endgroup$ Commented Aug 18, 2019 at 16:49
  • $\begingroup$ What is $v_a(b)$? $\endgroup$ Commented Aug 18, 2019 at 16:55
  • $\begingroup$ @SmileyCraft maximum power of $a$ dividing $b$, i.e. $\sum_{j \ge 1} 1_{a^j \mid b}$. It is quite standard. $\endgroup$ Commented Aug 18, 2019 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 18, 2019 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .