Consider a non-empty set of positive integers M. We know, that when some x is in M, then so are 4x and [sqrt(x)].
Determine all integers in M.
Note: For a real number x, [x] denotes the largest integer, that is smaller or equal to x.
since M is non-empty it either contains 1 or an integer greater than one. If it doesn't contain 1 then repeated application of [sqrt(x)] will eventually get you 1.
So now assume that the integer k is in M. If we wish to get to k+1 by repetition of [sqrt(x)] p times then we would need to start with an integer in the interval [(k+1)^(2p),(k+2)^(2p)). Now assume we could get into that interval by multiplying k by 4 q times. Thus we would need
(k+1)^2p<=4^q*k<(k+2)^2p
solving for q we get
(2p*ln(k+1)-ln(k))/ln(4)<=q<(2p*ln(k+2)-ln(k))/ln(4)
so we need this interval to contain an integer. If the difference between the end points is at least 1 then this is assured thus we need.
(2p*ln(k+2)-ln(k)-2p*ln(k+1)+ln(k))/ln(4)>=1
2p*ln((k+2)/(k+1))>=ln(4)
p>=ln(2)/ln((k+2)/(k+1))
Thus we can always find a way to get to k+1 from k.
Thus by induction all positive integers are in M.
|
|
Posted by Daniel
on 2020-01-20 03:36:38 |
proof
