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.


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Sieve of Squares


What if applet does not run?

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:

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:

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!

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)

Related material
Read more...

Sieves

  • Geometric view of the Sieve of Eratosthenes
  • Listing All the Composite Numbers
  • Lucky Numbers
  • Sieve of Eratosthenes
  • The Parabolic Sieve of Prime Numbers
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71493644