Sieve of SquaresA 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: 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:
In the central prison of Sikinia there are n cells numbered 1 to n, each occupied by a single prisoner. The state of each cell can be changed from closed to open and vice versa by a half-turn of the key. To celebrate the Centennial Anniversary of the Republic it was decided to grant a partional amnesty. The president sent an officer to the prison with the instruction:
A prisoner was freed if at the end his door was open. Which prisoners are set free? Remark: Do not think, just sieve! References
|Contact| |Front page| |Contents| |Algebra| |Store| Copyright © 1996-2012 Alexander Bogomolny |
| 40618399 |
