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.

Answer 3

Intuitively I believe the inner one is redundant, but I can't prove it.

You're not allowed to vote me down unless you can provide a value of x that proves me wrong. 8-)

Edit: See v3's comment on this answer for proof - thanks, v3!

Answer 4

The inner floor is redundant

Answer 5

The inner floor is redundant. A proof by contradiction:

Assume the inner floor is not redundant. That would mean that:

floor(sqrt(x)) != floor(sqrt(x+d))

for some x and d where floor(x) = floor(x+d). Then we have three numbers to consider: a = sqrt(x), b = floor(sqrt(x+d)), c = sqrt(x+d). b is an integer, and a < b < c. That means that a^2 < b^2 < c^2, or x < b^2 < x+d. But if b is an integer, then b^2 is an integer. Therefore floor(x) < b^2, and b^2 <= floor(x+d), and then floor(x) < floor(x+d). But we started by assuming floor(x) = floor(x+d). We've reached a contradiction, so our assumption is false, and the inner floor is redundant.

Answer 6

If x is an integer then the inner floor is redundant.

If x is not an integer then neither are redundant.

Answer 7

The outer floor is not redundant. Counterexample: x = 2.

floor(sqrt(floor(2))) = floor(sqrt(2)) = floor(1.41...)

Without the outer floor the result would be 1.41...

Answer 8

If the inner floor were not redundant, then we would expect that floor(sqrt(n)) != floor(sqrt(m)), where m = floor(n)

note that n - 1 < m <= n. m is always less than or equal to n

floor(sqrt(n)) != floor(sqrt(m)) requires that the values of sqrt(n) and sqrt(m) differ by at least 1.0

however, there are no values n for which the sqrt(n) differs by at least 1.0 from sqrt(n + 1), since for all values between 0 and 1 the sqrt of that value is < 1 by definition.

thus, for all values n, the floor(sqrt(n)) == floor(sqrt(n + 1)). This is in contradiction to the original assumption.

Thus the inner floor is redundant.

Answer 9

If n^2 <= x < (n+1)^2 where n is an integer, then

1. n <= sqrt(x) < n+1, so floor(sqrt(x)) = n;
2. n^2 <= floor(x) < (n+1)^2, so n <= sqrt(floor(x)) < n+1, so floor(sqrt(floor(x))) = n.

Therefore, floor(sqrt(floor(x))) = floor(sqrt(x)), which implies the inner floor is redundant.