What is the algorithm for switching lights to N?

Question

Today I came across this at an interview, and I'm completely at a standstill. Here is a description of the problem:

You have a set of lights from 1 to 100 in the room and 100 people. The 1st person enters the room and turns on all lights with numbers that are multiples of i. If this indicator is already on, they will turn it off (i.e., turn off the light). 100 - just a random number - the solution should work up to some arbitrary value N (N == number of lights == number of people).

For example, person 1 will turn on all the lights (since each number is a multiple of 1). Man 2 will switch all the lights that are a multiple of 2 (2,4,6,8, etc.). This continues until the 100th person.

At that time, I had the feeling that this might have something to do with trying to determine primes up to N, but I was not 100% sure, so I went with some kind of rude approach (here is something that I presented 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 everything was fine and good, until I get home and look at the inputs + outputs of this function. I did something like this to get some 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); 

This is long, so here is a snippet of output when # indicators 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, 3 indicators turn on. When the number of lights is between 16 and 24, 4 indicators turn on. Basically, it seems that when x light returns as an answer, the lower bound for the number of common lights is x ^ 2, and the upper bound is x (x + 2).

I am starting to see the structure here, but I can’t say if this result is an algorithm that I just don’t remember or don’t know about.

Answer 1

This problem is classically known as the “Locker problem” - there are many explanations on the Internet, for example:

http://mathforum.org/library/drmath/view/55812.html

Its essence is that those who have an even number of divisors will fall into the initial state, and those who have an odd number of divisors will be in the opposite state. This has little to do with being simple or not, although the divisors are really strong, well, a factor in it.

In particular, numbers that have an odd number of divisors are all ... drum ... perfect squares. Since any other divisor, except the square root, will have a matching and not equal divisor, but perfect squares have one additional divisor (square root) that does not connect to another divisor; he connects with himself.

---

Please note that for a particular problem, as you formulated it (how many of them are open), this means that the answer will be simply floor(sqrt(N)) for N lights, since the number of ideal squares will be less than or equal to N