Interesting behavior of $\frac{n}{v_2(n!)+1}$.

Question

I've lately noticed some interesting behavior from the values of the function $f(n)=\frac{n}{v_2(n!)+1}$, Where $v_p(n)$ is the $p$-adic valuation of $n$, and we also know that $v_p(n!)=\sum_{t=1}^\infty \left\lfloor \frac{n}{p^t} \right\rfloor$. I'll show the values of $f(n)$ for some values of $n$ below:

$(n,f(n))=(5,\frac{5}{4}),(10,\frac{10}{9}),(20,\frac{20}{19}),(30,\frac{10}{9}),(40,\frac{40}{39}),(50,\frac{25}{24}),(60,\frac{20}{19}),(100,\frac{50}{49}),...(900,\frac{300}{299}),(1000,\frac{200}{199})$

The first question that comes up is whether $f(n)>1$ for all $n>1$. To prove this, we need to prove $n>v_2(n!)+1$.

The second question is whether all $f(n)$s are in the form of a super particular ratio$(\frac{a+1}{a})$ for all values of $n$. For this happening, we need $\frac{1}{f(n)-1}$ to be a natural number. After some calculations, we should get to prove $n-(v_2(n!)+1)|n$. This seems unlikely to be true for all $n$, but I would like knowing the values of $n$ for which it holds, as I don't have any idea to approach this problem!

For the first problem i tried using the formula i mentioned earlier, and i got this:
$n>1+\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{2^2}}\rfloor+\lfloor{\frac{n}{2^3}}\rfloor+...$ But i don't know where to get from here, since we've got to deal with an infinite number of floors in the RHS!

I would appriecate any help :)

Edit: As Gerry Myerson pointed out, It seems that $f(p)$ for some prime numbers $p$ is in the form of $\frac{a+2}{a}$ instead. It would be nice to see for which prime numbers $p$ this happens, but still i have no idea in approaching this problems.

Answer 1

For the first part of the question, there is a theorem by Legendre (1808).

Let $p$ be a prime and let $n = a_k p^k + a_{k-1} p_{k-1} + \ldots + a_1 p + a_0$ be the base-$p$ expansion of $n$, we have $$v_p(n!) = \frac{n - (a_k + a_{k-1} + \ldots + a_1 + a_0)}{p-1}$$

Apply this to the case $p = 2$, we have $v_2(n!) = n - \alpha(n)$ where $\alpha(n)$ is the number of set bits in binary expansion of $n$. This implies $n \ge v_2(n!) + 1$ for all $n$.

For a proof of the theorem, see this.

Answer 2

The first place that answers the second question is $n=7$, as $\nu_2(7!)=4$, and we get $f(7)=7/5$, which is not of the form $(a+1)/a$. $f(11)=11/9$, $f(13)=13/11$, $f(19)=19/17$, $f(21)=21/19$ (so it's not just primes), ..., $f(46)=46/43$ (so it's not just odd numbers), .... I'm not confident that there's a simple & useful characterization of the counterexamples.

Answer 3

Well I myself came up with another proof for the second question, which i think is a little shorter (or more elementary) than what achille hui suggested using that theorem by Legendre. THe complete proof of mine is as following:

First, we will prove for each positive real number $x$, $2\lfloor x \rfloor \leq \lfloor 2x \rfloor$ (We call this Inequality I).
Assume $x=n+p$ for some integer $n$ and a real number $0\leq p<1$. Using this, we should prove $2\lfloor n+p \rfloor \leq \lfloor 2n+2p \rfloor$. by using basic floor function rules, we find out we should only prove $2\lfloor p \rfloor \leq \lfloor 2p \rfloor$. Because $p<1$ and $p$ is positive, so our case is proven completely. Also, the LHS is always $0$ and the RHS is always positive, and the equality holds only when $2p<1$ which means $0\leq p<0.5$.

Now, we first define $S=v_2(n!)=\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{2^2}}\rfloor+\lfloor{\frac{n}{2^3}}\rfloor+...$ By using Inequality I, we can say:
$2\lfloor \frac{n}{2^i} \rfloor \leq \lfloor \frac{n}{2^{i-1}} \rfloor$ . Using this several times, we can say $2(\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{2^2}}\rfloor+\lfloor{\frac{n}{2^3}}\rfloor+...)\leq \lfloor n \rfloor +\lfloor{\frac{n}{2}}\rfloor+\lfloor{\frac{n}{2^2}}\rfloor+\lfloor{\frac{n}{2^3}}\rfloor+...$ and $\lfloor n \rfloor = n$ so $2S\leq S+n$ which means $S\leq n$. Now we show that the LHS of on of the inequalities can be made larger in number by one, which in result makes $S+1\leq n$ which is the desired inequality.
We know that every natural number $n$ is between two powers of $2$, say $2^k\leq n<2^{k+1}$. By using $2\lfloor \frac{n}{2^i} \rfloor \leq \lfloor \frac{n}{2^{i-1}} \rfloor$ for case $i=k+1$ (which indeed is included in the sum) we have: $2\lfloor \frac{n}{2^{k+1}} \rfloor \leq \lfloor \frac{n}{2^{k}} \rfloor$ and also we have $2^k\leq n<2^{k+1}$ we have $1\leq \frac{n}{2^{k}} < 2$ and $\frac{n}{2^{k+1}}<1$. This means the RHS in the inequality is $1$ but the LHS is $0$. So we may assume the LHS in there inequality is exactly $1$ instead of $0$, because we already have the exact value of it in the RHS and we want to make the inequality stronger, which proves our result ($S+1\leq n$).