Search code examples
mathfloor

Which floor is redundant in floor(sqrt(floor(x)))?

I have floor(sqrt(floor(x))). Which is true:

  1. The inner floor is redundant.
  2. The outer floor is redundant.
Solution

  • Obviously the outer floor is not redundant, since for example, sqrt(2) is not an integer, and thus floor(sqrt(2))≠sqrt(2).

    It is also easy to see that sqrt(floor(x))≠sqrt(x) for non-integer x. Since sqrt is a monotone function.

    We need to find out whether or not floor(sqrt(floor(x)))==floor(sqrt(x)) for all rationals (or reals).

    Let us prove that if sqrt(n)<m then sqrt(n+1)<m+1, for integers m,n. It is easy to see that

    n<m^2 ⇒ n+1 < m^2+1 < m^2+2m+1 = (m+1)^2

    Therefor by the fact that sqrt is montone we have that

    sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1

    Therefor floor(sqrt(n))=floor(sqrt(n+eps)) for all 0<eps<1 and integer n. Assume otherwise that floor(sqrt(n))=m and floor(sqrt(n+eps))=m+1, and you've got a case where sqrt(n)<m+1 however sqrt(n+eps)>=m+1.

    So, assuming the outer floor is needed, the inner floor is redundant.

    To put it otherwise it is always true that

    floor(sqrt(n)) == floor(sqrt(floor(n)))

    What about inner ceil?

    It is easy to see that floor(sqrt(n)) ≠ floor(sqrt(ceil(n))). For example

    floor(sqrt(0.001))=0, while floor(sqrt(1))=1

    However you can prove in similar way that

    ceil(sqrt(n)) == ceil(sqrt(ceil(n)))