We are given a sequence a1, a2, ... , an. Each ai can take the values 0 or 1. Initially, all ai = 0. We now successively carry out steps 1, 2, ... , n. At step m we change the value of ai for those i which are a multiple of m. Show that after step n, ai = 1 iff i is a square. Devise a similar scheme give ai = 1 iff i is twice a square.
ai is changed once for each divisor of i. If i is non-square then it has an even number of divisors (they come in pairs d, i/d), so ai ends as 0. If i is square it has an odd number of divisors and so ai ends as 1.
We change those that a multiple of 2, then those that are a multiple of 4, then those that are a multiple of 6 and so on. This only affects the even numbers and indeed a2i is changed once for each divisor of i, so the same argument as before shows that a2i ends as 1 iff i is a square. Note that a2i+1 is never changed, so it remains 0.
28th Putnam 1967
© John Scholes
14 Jan 2002