10
$\begingroup$

I want to solve the following inequality for $a$ :

$$\left \lfloor \frac{a}{b} \right \rfloor > \frac{a}{b+1}$$

Where both $a$ and $b$ are strictly positive integers.

My end goal with this is, for a given $b$, to be able to find the smallest $a$ of the form $6 \times 10^{7+p}$ ($p \in \mathbb{Z}$)

If you would like to known more about the context :

I stumbled upon this problem while coding a musical file format converter.

In one file format, the BPM of the song is stored as some integer version of $$\frac{6 \times 10^7}{\textrm{BPM}}$$ which I call the tempo value.

My code internally handles decimal BPMs, so it needs to convert back and forth between the two "representations". I wanted this conversion to be both "idempotent" and "minimal" in some way, "idempotent" as in : if I convert a tempo value to a BPM and back, I get the same value, and "minimal" meaning that the intermediate BPM is stored with the minimum number of decimal places needed to recover the exact tempo value if I just floor the "raw" conversion on the way back. if $v$ is the tempo value, the "raw" BPM can be computed as $$\textrm{BPM}_\textrm{raw} = \frac{6 \times 10^7}{v}$$ I then need to choose some number of decimal places $p$ to truncate it to, which (thanks wikipedia) can be expressed this way : $$\textrm{BPM}_\textrm{trunc} = \textrm{floor(}\textrm{BPM}_\textrm{raw}, p\textrm{)} = \frac{\left \lfloor 10^p \cdot \textrm{BPM}_\textrm{raw} \right \rfloor}{10^p}$$ And then to convert it back to an integer tempo value, I reuse the formula then floor the result again : $$v_\textrm{recovered} = \left \lfloor \frac{6 \times 10^7}{\textrm{BPM}_\textrm{trunc}} \right \rfloor$$ Plugging every formula together, I want to find a condition on p that satisfies : $$ \begin{align} v &= v_\textrm{recovered} \\ v &= \left \lfloor \frac{6 \times 10^7}{\textrm{BPM}_\textrm{trunc}} \right \rfloor \\ v &= \left \lfloor \frac{6 \times 10^7}{\frac{\left \lfloor 10^p \cdot \textrm{BPM}_\textrm{raw} \right \rfloor}{10^p}} \right \rfloor \\ v &= \left \lfloor \frac{6 \times 10^7}{\frac{\left \lfloor 10^p \cdot \frac{6 \times 10^7}{v} \right \rfloor}{10^p}} \right \rfloor \\ v &= \left \lfloor \frac{6 \times 10^{7+p}}{\left \lfloor \frac{6 \times 10^{7+p}}{v} \right \rfloor} \right \rfloor \\ \end{align} $$ If we rename $v$ to $b$ and $6 \times 10^{7+p}$ to $a$ we need to find a condition on $a$ so that $$b = \left \lfloor \frac{a}{\left \lfloor \frac{a}{b}\right \rfloor}\right \rfloor$$ $b$ is equal to the floor of that fraction if and only if the value of that fraction sits between $b$ and $b+1$ exclusive, which translates to $$ b \leq \frac{a}{\left \lfloor \frac{a}{b}\right \rfloor} < b+1$$ The left part is true, this comes from the fact that $\left \lfloor x \right \rfloor \leq x$ for any $x$, plugging in $\frac{a}{b}$ gives $$\left \lfloor \frac{a}{b} \right \rfloor \leq \frac{a}{b} \Leftrightarrow \frac{a}{\frac{a}{b}} \leq \frac{a}{\left \lfloor \frac{a}{b} \right \rfloor} \Leftrightarrow b \leq \frac{a}{\left \lfloor \frac{a}{b} \right \rfloor}$$ So I just need to find a condition for the right side, which can be rewritten a bit : $$\frac{a}{\left \lfloor \frac{a}{b}\right \rfloor} < b+1 \Leftrightarrow \frac{a}{b+1} < \left \lfloor \frac{a}{b}\right \rfloor$$ And here we are ...

$\endgroup$
4
  • 4
    $\begingroup$ This is a great first question. You included your work, amazing context, and more. $\endgroup$ – Tyma Gaidash May 18 at 14:52
  • 1
    $\begingroup$ The smallest positive integer $n$ for which $n \not =\left \lfloor \dfrac{6 \times 10^{7}}{\left \lfloor \frac{6 \times 10^{7}}{n} \right \rfloor} \right \rfloor $ is $7768$, slightly more than $\sqrt{6 \times 10^{7}}$ and a very high number of beats per minute $\endgroup$ – Henry May 19 at 0:01
  • $\begingroup$ Related context Why are some song tempos not even BPMs? $\endgroup$ – smci May 19 at 1:09
  • $\begingroup$ You say you are truncating not rounding, btw. $\endgroup$ – smci May 19 at 1:12
4
$\begingroup$
  1. The floor function obeys$$\mathrm{ bn\le a<b(n+1),y=b, n\in\Bbb N}$$ Graph,
  2. Using the identity above: $$\mathrm{y_1=b=\left\lfloor\frac ab\right\rfloor>y_2=\frac a{b+1}}$$
  3. Therefore when we let a vary:$$\mathrm{a>b(b+1)=b^2+b, bn\le a<b(n+1),y=b, a,b,n\in\Bbb N}$$
  4. Graphical proof

But this only gives the bound when the two graphs no longer cross and $a\ge \left\lfloor \frac ab \right \rfloor$. Modifying this a little bit after doing some pattern analysis of the inequalities satisfying b=1,2,... gives: $$\mathrm{a>n,b(n+1)\le a <(b+1)(n+1)=bn+b+n+1, a,b,n \in \Bbb N^0}$$

or simply: $$\mathrm{a>n,b(n+1)\le a <(b+1)(n+1)=bn+b+n+1, a,b,n \in \Bbb N^0, n\le b,\ if\ n=b,\ then \ a>b^2,\ or\ otherwise\ undefined}$$ Here is graphical proof of this one.

All in all:$$\mathrm{p>log_{10}(n)-7,0\le a-b(n+1)=10^{7+p}-bn-b<n+1⇔log_{10}(b)+log_{10}(n+1)-7 \le p < log_{10}(b+1)+log_{10}(n+1)-7, a,b,n\in \Bbb N^0=0,1,2,...,p\in\Bbb Z}$$

I will leave it to you to find other forms and edit my solutions.

These formulas even work with $a=x^x$ and other functions. Please correct me and give me feedback!

$\endgroup$
1
  • $\begingroup$ How about the other great answer? Thanks for the “checkmark”. $\endgroup$ – Tyma Gaidash May 19 at 11:42
3
$\begingroup$

Let $a=bk+r$, where $0\leq r\leq {b-1}.$ Then we have, $\lfloor {\frac ab} \rfloor=k.$ So, $k>\frac {a}{b+1}.$ So that, $bk+k>bk+r.$ Which means, $k>r$. So, the range will be $a>b(r+1).$ So the range of $a$ for which your inequality is satisfied depends upon what $a$ mod $b$ is. But $a>b^2$ will invariably give safe values.

$\endgroup$

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.