What is the algorithm for toggling lights up to N?

Question

I encountered this in a job interview today, and I'm totally stumped. Here's a description of the problem:

You have a set of lights from 1 to 100 inside a room, and 100 people. The i-th person walks into the room and turns on all the lights numbered that are a multiple of i. If that light is already turned on, they will turn it off (i.e. they will toggle the light). 100 is just random number -- the solution should work up to some arbitrary value N (N == number of lights == number of people).

For instance, person 1 will turn on all the lights (as every number is a multiple of 1). Person 2 will toggle all the lights that are a multiple of 2 (2,4,6,8, and so on). This continues up to the 100th person.

At the time, I got the feeling that this might have something to do with trying to determine prime numbers up to N, but I wasn't 100% sure, so I went with a kind of brute force approach (here's roughly what I provided in PHP):

function lights_toggled($number_of_lights) {
  $toggly = function($idx, $lights) {
    foreach($lights as $i => $light) {
      if($i % $idx == 0) {
        if($lights[$i]) {
          $lights[$i] = 0;
        } else if(!$lights[$i]) {
          $lights[$i] = 1;
        } 
      } 
    } 
    return $lights;
  };

  $lights = array_fill(1,$number_of_lights,0);
  for($i = 1; $i <= count($lights); $i++) {
    $lights = $toggly($i, $lights);
  }
  return array_sum($lights);
}

I thought all was well and good, until I got home and started looking at inputs + outputs of this function. I did something like this to get some sample results:

$results = array();
for($j = 1; $j <= 100; $j++) {
  $number_of_lights_on = lights_toggled($j);
  $results[$number_of_lights_on][] = $j;
}
print_r($results);

It's long, so here's a snippet of the output for when # of lights ON == 3 or 4:

...
[3] => Array
    (
        [0] => 9
        [1] => 10
        [2] => 11
        [3] => 12
        [4] => 13
        [5] => 14
        [6] => 15
    )

[4] => Array
    (
        [0] => 16
        [1] => 17
        [2] => 18
        [3] => 19
        [4] => 20
        [5] => 21
        [6] => 22
        [7] => 23
        [8] => 24
    )
...

When the number of lights is between 9 and 15, the answer is 3 lights on. When the number of lights is between 16 and 24, the answer is 4 lights on. Basically, it seems when when x lights returns as the answer, the lower bound of number of total lights is x^2 and it's upper bound is x(x+2).

I am starting to see structure here, but I can't put my finger on whether this result follows an algorithm that I just don't remember or know about.

Answer 1

This problem is classically known as the "Locker Problem" - there are many explanations of it around the web, such as this one:

Link

The gist of it is that the ones which have an even number of divisors will end up in their starting state, while the ones that have an odd number of divisors will end up in the opposite state. This doesn't really have much to do with being prime or not, though divisors do heavily, well, factor into it.

In particular, the numbers which have an odd number of divisors are all.... drumroll... perfect squares. Since any other divisor except the square root will have a matching and non-equal divisor, but perfect squares have one extra divisor (the square root) which doesn't pair up with another divisor; it pairs with itself.

---

Note that for the particular problem as you phrased it (how many are open), that means the answer will simply be floor(sqrt(N)) for N lights, since that's how many perfect squares will be less than or equal to N.