Delete all the squares from the sequence 1, 2, 3, ... . Show that the nth number remaining is n + m, where m is the nearest integer to √n.
Any integer N in the sequence lies between k2 and (k + 1)2 for some k, and hence N = k2 + h for some k and some h such that 1 ≤ h ≤ 2k.
Since there are just k squares smaller than N, N is the (N - k)th number in the sequence. But (k - 1/2)2 < k2 - k + 1 ≤ N - k ≤ k2 + k < (k + 1/2)2, so the nearest integer to the square root of (N - k) is k and N = n + m, where n = N - k and m is the nearest integer to the square root of n.
27th Putnam 1966
© John Scholes
25 Jan 2002