For $g(n) = \sum_{d|n}f(d)$, find $g(5000)$.

Question

This is the second part of my previous question asked here. Thanks to your help, I was able to understand why the following function $f(n)$ is multiplicative:

$f(n)$ is the greatest power of $2$ that divides $n$.

For example, $f(20) = 2^2 = 4$, $f(32) = 2^5 = 32$, f$(72) = 2^3 = 8$, etc.

I require some help on the next part of the question I'm practicing for my final exam in number theory. The second part is as follows:

Find $g(5000)$ for $$g(n) = \sum_{d|n}f(d)$$

From my understanding, as $f(n)$ is multiplicative, $g(n)$ must also be multiplicative, but I'm not sure how to find the actual value of $g(5000)$. I know that $5000 = 2^3 \cdot 5^4$ and so $f(5000) = 2^3 = 8$.

I think I'm a bit confused about the function itself, am I supposed to be summing the divisors of $n = 5000$ or $f(n) = 8$?

I could be completely wrong, so feel free to correct me. Thanks for any help!

Answer 1

This is essentially @Crostul comment.

You have $g$ is multiplicative ($g=1\ast f$ is the convolution of two multiplicative functions, hence multiplicative)

Multiplicative means that $g(mn)=g(m)g(n)$ when $\gcd(m,n)=1$. In particular a multiplicative function is determined by the values of it in prime powers. So, our question would be what is $g(p^k)$?

If $p=2$: Then $$g(2^k)=\sum_{d|2^k}f(d)=\sum_{0\leq j\leq k}f(2^j)=\sum_{0\leq j\leq k}2^j=2^{k+1}-1$$ If $p\neq 2$: Then $$g(p^k)=\sum_{d|p^k}f(d)=\sum_{0\leq j\leq k}f(p^j)=\sum_{0\leq j\leq k}1=k+1$$

In particular, we have $5000=2^35^4$. Hence, $$g(5000)=g(2^3)g(5^4)=(2^4-1)(4+1)=(15)(5)=75$$

Answer 2

you have to find the set of $d$ that divide $n$

$5000 = 2^35^4$

factors are $1,5,25,125,625,2,10,50,250,\cdots,8,40,200,1000,5000$

$g(5000) = f(1)+ f(5) + \cdots + f(1000)+ f(5000) = 4(2^0+2^1+2^2+2^3) = 4(2^4-1) = 60$

Answer 3

Here’s an intuitive approach to this problem.

Clearly, 5000 = $2^{3}*5^{4}$ which implies that it has 20 divisors. Out of these 20 divisors, 5 are of the form $2^{3}*5^{p}$, where $0 <= p <= 4$. Similarly, 5 are of the form $2^{2}*5^{p}$, where $0 <= p <= 4$ and so on till $ 2^{0}$.

Therefore, $g(n)$ = $\sum_{d|n} f(d)$ = 8x5 + 4x5 + 2x5 + 1x5 = 75.

Edit: I actually misunderstood the question earlier. I added the $k$’s in $2^{k}$ not the $2^{k}$’s.