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

Question

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

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

Answer 1

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)))

Answer 2

The inner one is redundant, the outer one of course not.

The outer one is not redundant, because the square root of a number x only results in an integer if x is a square number.

The inner one is redundant, because the square root for any number in the interval [x,x+1[ (where x is an integer) always lies within the interval [floor(sqrt(x)),ceil(sqrt(x))[ and therefore you don't need to floor a number before taking the square root of it, if you are only interested the integer part of the result.