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.
|What if applet does not run?|
The factors of a number come in pairs:
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:
for i:=1 to n do
turn the keys of cells i, 2i, 3i, ... .
A prisoner was freed if at the end his door was open. Which prisoners are set free? Remark: Do not think, just sieve!
- A. Engel, Exploring Mathematics with Your Computer, MAA, 1993
- P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004 (Locker doors puzzle)
Copyright © 1996-2018 Alexander Bogomolny