We are given a sequence a_{1}, a_{2}, ... , a_{n}. Each a_{i} can take the values 0 or 1. Initially, all a_{i} = 0. We now successively carry out steps 1, 2, ... , n. At step m we change the value of a_{i} for those i which are a multiple of m. Show that after step n, a_{i} = 1 iff i is a square. Devise a similar scheme give a_{i} = 1 iff i is twice a square.

**Solution**

a_{i} 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 a_{i} ends as 0. If i is square it has an odd number of divisors and so a_{i} 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 a_{2i} is changed once for each divisor of i, so the same argument as before shows that a_{2i} ends as 1 iff i is a square. Note that a_{2i+1} is never changed, so it remains 0.

© John Scholes

jscholes@kalva.demon.co.uk

14 Jan 2002