Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$

Question

I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$?

Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$. First of all, we want to find a recurrence for $g(n)$. If n is odd, then it is pretty easy to see that $g(n)=g(n−1)$. If n is even, try to write $g(n)$ in terms of $g(n/2)$.

Can someone help thanks.

That the only definition of f given

That the only definition of f I have from above question which basically like a remainder of 0 in a binary number like how many 0 are after last 1

Here is the screen shot of the question

Answer 1

Hints:

$(2k+1)! = \begin{array}{l}\color{grey}{1~~\cdot 3~~\cdot 5~~\cdot 7~~\cdots (2k-3)~~~~\cdot (2k-1)~~~\cdot(2k+1)}\\~~\cdot 2~~\cdot 4~~\cdot 6~~\cdot 8\cdots~~~~\cdot(2k-2)~~~~~\cdot (2k)\end{array}$

Noting that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k+1)!$ we see that $g(2n+1)=g(2n)$.

$(2k)! = \begin{array}{l}\color{grey}{1~~\cdot 3~~\cdot 5~~\cdot 7~~\cdots (2k-3)~~~~\cdot (2k-1)}\\~~\cdot 2~~\cdot 4~~\cdot 6~~\cdot 8\cdots~~~~\cdot(2k-2)~~~~\cdot(2k)\end{array}$

$=\color{grey}{(1\cdot 3\cdot 5\cdots (2k-3)\cdot (2k-1))}\cdot (2\cdot 4\cdot 6\cdots (2k-2)(2k))$

$=\color{grey}{(1\cdot 3\cdot 5\cdots (2k-3)\cdot (2k-1))}\cdot ((2\cdot 1)\cdot (2\cdot 2)\cdot (2\cdot 3)\cdots (2\cdot(k-1))\cdot (2\cdot k))$

$=\color{grey}{(1\cdot 3\cdot 5\cdots (2k-3)\cdot (2k-1))}\cdot 2^k\cdot k!$

Notice that the odd factors in grey contribute nothing to the largest power of $2$ which divides $(2k)!$

You should be able now to recognize the relationship between $g(2k)$ and $g(k)$. Armed with this knowledge, you should be able to find $g(8000000000000)-g(4000000000000)$ with almost no effort.

Additional hint:

Recognize that $g(2k)$ counts the number of factors of $2$ occurring in $(2k)!$ and $g(k)$ counts the number of factors of $2$ occurring in $k!$. Recognize that $(2k)!$ is equal to an odd number (which has no factors of $2$) times $2^k$ times $k!$. So, the only additional factors of $2$ which are present between $(2k)!$ and $k!$ are those that occur as a result of $2^k$.

Solution:

$g(2n)-g(n)=n$

---

The above helps us to come up with a recursive definition for $g$, but it is not particularly helpful for finding a closed form for $g$ (that I immediately see).

That being said, when calculating $g(n)$ notice that every multiple of $2$ less than or equal to $n$ will contribute one to the total of the largest exponent of $2$ that divides $n!$. Further, each multiple of four less than or equal to $n$ will contribute yet an additional one to the total, and further each multiple of eight will and so on.

You should be able to formalize these observations in order to express $g(n)$ in closed form using an infinite sum.

This should remind you a great deal of the problem of counting how many trailing zeroes are at the end of a factorial, see for example here.