Sieve of Squares

A slight modification of the Sieve of Eratosthenes produces an interesting result. Write integers from 1 through a given number N in order. Originally, all the numbers are typed in blue and are enclosed in squares. Proceed in steps. On a step #k, change the color of all multiples of k (including k itself) from blue to red or from red to blue as the case may be. The red numbers are circled. Perform N steps, from 1 through N. What numbers will be red and circled?

In the applet below, pay attention to the button at the bottom of the applet, initially labelled "1". "1" indicates the first step. Click on the button. The first step will be performed, and the label on the button will change to "2" - a sign that the applet is ready for the next step, etc.

The factors of a number come in pairs: A = n·m. This shows that the effect of actions on steps #n and #m cancel out so long as the factors n and m are different. If A is a complete square, A = n·n, the step #n is still performed, but only once, which causes A to be red when the process stops.

I first noticed this problem in [Winkler, p. 13], but then ran into it in [Engel, p. 41 as an exercise. Winkler sets up the problem in a locker room where coming students lock/unlock the lockers to confirm with the above problem. Engel's setup is quite different. He does not present a solution. Instead, he urges the reader to perform the sieve:

References

1. A. Engel, Exploring Mathematics with Your Computer, MAA, 1993
2. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004 (Locker doors puzzle)

Copyright © 1996-2009 Alexander Bogomolny