Is $\left\lfloor \frac{n}{p^i}\right\rfloor>\frac{n}{p^{i+1}}$, for $n\ge1$, $p\le n$ any prime, and $0\le i\le\lfloor \log_p n\rfloor$?

66 Views Asked by At

Is this inequality always true $$\frac{\bigg\lfloor \frac{n}{p^i}\bigg\rfloor}{n}-\frac{1}{p^{i+1}}\ge 0\,?$$

$n$ is a positive integer, $p\le n$ is a prime and $i$ is any integer from $0$ to $\lfloor \log_p n\rfloor$. The upper bound for $i$ comes from the fact that, given $p$, I want to consider $i$ such that $p^i\le n$ (so that the floor in the inequality is at least 1.

The bound $\bigg\lfloor \frac{n}{p^i}\bigg\rfloor\ge\frac{n}{p^i}-1$ cannot be used since the inequality won't be true in that case.

Using Mathematica, I haven't been able to find a counterexample for $n$ up to $500$. Here's the code used:

Table[Table[ Table[Floor[n/Prime[p]^i]/n >= 1/Prime[p]^(i + 1), {i, 0, Floor[Log[n]/Log[Prime[p]]]} ], {p, 1, PrimePi[n]}], {n, 1, 500}]

1

There are 1 best solutions below

3
On BEST ANSWER

Let $n=q\cdot p^i+r$ where $0\leq r<p^i$, $q\in \mathbb{N}$. $$ \frac{\bigg\lfloor \frac{n}{p^i}\bigg\rfloor}{n}-\frac{1}{p^{i+1}}=\frac{q}{n}-\frac{1}{p^{i+1}}=\frac{q\cdot p^{i+1}-n}{n\cdot p^{i+1}}. $$ Take $n=q\cdot p^i+r$ into $q\cdot p^{i+1}-n$ get $q\cdot p^{i+1}-n=q(p^{i+1}-p^i)-r>0$.