Determine all possible values of a nonnegative integer k, such that k is NOT expressible in the form:
N+floor(√N+1/2)
for some integer N.
*** Adapted from a problem appearing in the IMO longlist.
We are given k(n) = n + floor[sqrt(n) + 1/2]
So then evaluating k at n+1 yields k(n+1) = n+1 + floor[sqrt(n+1) + 1/2]
Then what is k(n+1)-k(n)?
floor[sqrt(n+1) + 1/2] and floor[sqrt(n) + 1/2] will be equal for any integer n in most cases; the exception is when the fractional part of sqrt(n+1) begins with .5 while the fractional part of sqrt(n) begins with .4
Let m be the integer such that m ~= sqrt(n) + 1/2. Then m^2-m+0.25 ~= n. Dropping the 0.25 takes us back to integers, so then let n = m^2-m.
So then the values of n of the form m^2-m are the ones where floor[sqrt(n+1) + 1/2] and floor[sqrt(n) + 1/2] will be two distinct values.
So then this means that k(n+1)-k(n) will be 1 in most cases and 2 in the exceptional cases. Thus the sequence k will be mostly consecutive integers, with a few jumps of 2. KS wants to know which integers are being skipped.
n=m^2-m is where the skip occurs. These will then correspond to the integer after k(m^2-m).
k(m^2-m) = m^2-m + floor[sqrt(m^2-m) + 1/2]
= m^2-m + floor[sqrt((m-1/2)^2 - 1/4) + 1/2]
< m^2-m + floor[sqrt((m-1/2)^2) + 1/2)]
= m^2-m + floor[m-1/2+1/2]
= m^2-m + m = m^2
Then k(m^2-m) < m^2 means we have k(m^2-m) = m^2-1
Therefore the integers that gets skipped in the series for k is integers of the form m^2.
Solution?
