### 27th Putnam 1966

**Problem A4**

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.

**Solution**

Any integer N in the sequence lies between k^{2} and (k + 1)^{2} for some k, and hence N = k^{2} + 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} < k^{2} - k + 1 ≤ N - k ≤ k^{2} + 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

jscholes@kalva.demon.co.uk

25 Jan 2002