|
M contains all positive integers.
By repeatedly taking the [sqrt(x)] function (call it "isqrt") of some element in M, we see that 1 is in M. It follows that all powers of 4 are in M. So far, so obvious.
To complete the proof, we show that for any positive integer n, there is a power of 4, that results in n when repeatedly applying isqrt.
Which numbers give n when applying isqrt once? All numbers in the interval
I_1 := [ n^2, (n+1)^2 )
Likewise, all numbers in
I_2 := [ n^4, (n+1)^4 )
end up in n when isqrt is applied twice. Generally
I_m := [ n^(2^m), (n+1)^(2^m) )
shrinks to n when applying isqrt m times.
Since (n+1)/n > 1, the quotient of right and left interval of I_m goes to infinity when m goes to infinity. But every interval [a,b] where b/a > 4, contains a power of 4. Therefore, some I_m contains a power of 4.
See also Daniel's comment for a (slightly) different proof. |
