We define $f(n) = max \{k \in \mathbb{N} \text{, such that $2^k$ divides n} \}$. As an example, $f(99) = 0$, $f(5) = 0$, $f(12) = 2$, $f(14) = 1$. Now further let's define $g(n) := f(n!)$. Finding a recurrence, if $n$ is odd then $g(n) = g(n-1)$. How can we write $g(n)$ in terms of a closed formula?
How can we describe the even variant in terms of $g(n/2)$? And if we can describe it, what would be the closed formula for two evens $a,b$ for the equation $g(a) - g(b)$? As an example $g(8.000.000.000.000) - g(4.000.000.000.000) = ?$
The highest power of $2$ that divides $x!$ is $$\sum_{n=1}^{\infty}[\frac{x}{2^n}]$$ Which can be shown by counting techniques. Thus we get $$g(x)=\sum_{n=1}^{\infty}[\frac{x}{2^n}]$$ From this, we get $$g(2x)= \sum_{n=1}^{\infty}[\frac{2x}{2^n}]=\sum_{n=1}^{\infty}[\frac{x}{2^{n-1}}]$$ $$=\sum_{n=0}^{\infty}[\frac{x}{2^n}]$$ $$=x+\sum_{n=1}^{\infty}[\frac{x}{2^n}]$$ $$=x+g(x)$$ From this we get $g(2n)=n+g(n)$
If we take $n=2^km$, where $m$ is odd, we have $$g(n) = g(2^km)= 2^{k-1}m+2^{k-2}m+....+2m+m+g(m)= 2^km-m+g(m)$$ $$=n-m + g(m-1)$$ w=We can repeat this again with $g(m-1)$ to get $$g(n)=n-m +(m-1)-.... -(2^l+1)+(2^l-1)= n-\sum 1 $$ Where $l$ is aninteger
The number of times we add $1$ in the above summation of $1$ is the number of times we have to apply the recursive algorithm. But the number of times we apply the algorithm is the same as the number of ones in the binary expansion of $n$. From this we get $$g(n)=n-k\text{ k=number of 1s in binary expansion of n}$$ This is the closed form of $g(n)$ for all $n$