Reasoning about floor functions and exponents

Question

Let $a,t$ be integers such that:

• $t > a \ge 0$
• $t > 1$

It seems to me that there exists integers $r,w$ such that:

$a = \left\lfloor\dfrac{t^w}{r}\right\rfloor$

I'm having trouble coming up with the argument.

Consider $a=4, t = 10$.

There is no $r$ for $w = 1$.

For $w = 2$,

$$4 = \left\lfloor\dfrac{10^2}{25}\right\rfloor$$

Am I right in my assumption about the general case? If so, how can this be shown?

Answer 1

This is quite trivial. Make $w$ large enough so that: $$\frac{t^w}{a}-\frac{t^w}{a+1}>2$$ Then, there exists some integer $r$ in between $\frac{t^w}{a}$ and $\frac{t^w}{a+1}$. We then have: $$\frac{t^w}{a}>r>\frac{t^w}{a+1} \implies a<\frac{t^w}{r}<a+1$$ Which gives us: $$\bigg\lfloor \frac{t^w}{r} \bigg\rfloor=a$$ Solved!

Answer 2

We need

$a \le \frac {t^w}r < a+1$

$ar \le t^w < ar+ r$.

Now we can make $w$ and $t^w$ as large as we like. But for any value of $t^w$ and $a$ there a greatest integer $n$ (maybe $0$) so that $an \le t^w < a(n+1)=an+ a$.

And if we happen to have $a < n$ we'd have $an \le t^w < an+a < an + n $ and we could let $r=n$.

And to do that all we need is to choose a $w$ so that $t^w> a^2$. Then to have $an \ge t^w>a^2$ we'd have to have $n \ge a$.

And that's it.

Simply let $w$ be so that $t^w > a^2$ and let $r = [\frac{t^w}a]$.

Let's take for instance, $a=31$ and $t=2$. We need to find a $w$ so that $2^w >31^2$. Now $31^2 < 1000$ and $2^{10} > 1000$ so let take $w=10$. We want $31r < 2^{10} < 31(r+1)$ or in other words $r< \frac {2^{10}}{31} <r+1$.... calculator time... $r =33$

Now we have $31*33 < 2^{10} < 31*33+31 < 31*33 + 33$ and so

$31 < \frac {2^{10}}{33} < 32$ so $31 = [\frac {2^{10}}{33}]$

Answer 3

By the division algorithm, for every such $a,t$ and $w$ as described above there are unique non-negative numbers $r,q$ with $r<a$ such that $t^w=aq+r$ and thus $\frac{t^w}{q}=a+\frac{r}{q}$. So, if $\frac{r}{q}<1$ then we would have $\lfloor\frac{t^w}{q}\rfloor=\lfloor a+\frac{r}{q}\rfloor=a$. Let $w'$ be such that in $t^{w'}=aq'+r'$ (so that $r',q'$ are as in the division algorithm) $q'>a$ (such a $q'$ must exist lest $aq'+r'$ take on finitely many values while $t^{w'}$ takes on infinitely many). Then $\frac{r'}{q'}<\frac{a}{q'}\leq\frac{a}{a+1}<1$ as desired so that $$\lfloor\frac{t^{w'}}{q'}\rfloor=\lfloor a+\frac{r'}{q'}\rfloor=a$$