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}]

  • $\begingroup$ Please see edited title to avoid awkward typings in the future. $\endgroup$ – Did Oct 1 '17 at 6:04

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$.

  • $\begingroup$ What is the base for the "$n=q\cdot p^i+r$ where $0\leq r<p, q\in \mathbb{ℕ}$." statement? If you convert $n$ to base $p$, will you always obtain such a result? $\endgroup$ – rtybase Oct 1 '17 at 10:17
  • $\begingroup$ @rtybase It should be $0\leq r < p^i$, my mistake. $\endgroup$ – yahoo Oct 1 '17 at 10:21
  • $\begingroup$ Yep, much better now, +1 ;) $\endgroup$ – rtybase Oct 1 '17 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.