I tried to do some math in a blog post of mine and came to one with a floor function. I wasn't sure how to deal with it so I just ignored it, and then added the ceiling function in my final equation as that seemed to give me the result I wanted. I'm wondering what is the correct way of handling these functions in equations?

What I did was this:

$$\begin{align} G(n) &= \left\lfloor n\log{\varphi}-\dfrac{\log{5}}{2}\right\rfloor+1 \\\\ n\log{\varphi} &= G(n)+\dfrac{\log{5}}{2}-1 \\\\ n &= \left\lceil\dfrac{G(n)+\dfrac{\log{5}}{2}-1}{\log\varphi}\right\rceil \end{align}$$

How should I have done this in a correct way? How do I work with the ceiling and floor functions when I shuffle around with equations?

  • 3
    $\begingroup$ The floor and ceiling functions are very very deep and have very interesting connections to analytic number theory and modular forms. You might be surprised to hear this, but they are not so easy to manipulate algebraically. $\endgroup$ – user126 Nov 5 '10 at 5:11

You can replace $\lfloor x \rfloor$ with $x - \theta$, where $\theta \in [0,1)$ is some unknown quantity. Similarly, $\lceil x \rceil = x + \theta$ (a different $\theta$ within the same range).

Another helpful identity is $\lfloor x \rfloor + n = \lfloor x + n \rfloor$ for any integer $n$.

  • $\begingroup$ wow, that's a pretty nifty substitution. is it reasonable to manipulate the $\theta$ identically to any other symbol, then recombine it with something at the end to reintroduce the floor or ceiling function into your final result? Somehow that seems like it could have hidden pitfalls $\endgroup$ – Ken Bellows Jul 15 '16 at 13:07
  • $\begingroup$ It's reasonable as long as in the end you check that the $\theta$ part lies in $[0,1)$ and $x-\theta$ or $x+\theta$ (as the case may be) is an integer. $\endgroup$ – Yuval Filmus Jul 15 '16 at 13:09

Your final expression gives you the number you want.

According to your blog post, you're looking for the smallest integer $n$ (i.e., the "first Fibonacci number with 1000 digits") that satisfies $$G(n) = \left\lfloor n \log \varphi - \frac{\log 5}{2} \right\rfloor + 1.$$ There may, of course, be more than one integer $n$ for which this is true.

By definition of the floor function, the values of $n$ that satisfy this are the values that satisfy $$G(n) - 1 \leq n \log \varphi - \frac{\log 5}{2} < G(n),$$ which, since $\log \phi > 0$, are the values that satisfy $$\frac{G(n) + \frac{\log 5}{2}}{\log \varphi} - \frac{1}{\log \varphi} \leq n < \frac{G(n) + \frac{\log 5}{2}}{\log \varphi}.$$

Since $\frac{1}{\log \varphi} \approx 4.78$, there are either four or five integers in this interval. But the smallest one is obtained by taking the ceiling of the lower endpoint of the interval; i.e., $$\left\lceil\frac{G(n) + \frac{\log 5}{2} - 1}{\log \varphi}\right\rceil.$$

Incidentally, this argument also apparently shows that there are either four or five Fibonacci numbers that have a given number of digits. (Except in the single-digit case, where there are six (not counting 0). But your formula for $G(n)$ doesn't hold when $n=1$, so we shouldn't expect this calculation to be true in the single-digit case anyway.)


Observe that \begin{eqnarray} G(n) = \left \lfloor n \log \varphi - \log \sqrt{5} \right \rfloor + 1 = \left \lceil n \log \varphi - \log \sqrt{5} \right \rceil \end{eqnarray} and write \begin{eqnarray} \left \lceil \frac{G(n)}{\log \varphi} + \log_{\varphi} \sqrt{5} \right \rceil & = & \left \lceil \tfrac{1}{\log \varphi} \left \lceil n \log \varphi - \log \sqrt{5} \right \rceil + \log_{\varphi} \sqrt{5} \right \rceil = n. \end{eqnarray}


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.