Infinity Hotel problem

Q. Welcome to the infinity hotel has an infinite number of rooms $1,2,3,4,...$ The manager notices all of the rooms have the lights on. He flips the switch every other one. (Rooms $2, 4, 6, …$) Then he does the same thing with every third room. (Rooms $3, 6, 9, …$) Then he does the same with every fourth room. (Rooms $4, 8, 12, …$) So on, and so forth, the process continues on forever. Of the first million rooms, how many lights get left on.

So I know by testing cases that all the prime number rooms will be left off because the only divisors are 1 and itself so when he gets to the prime, he just shuts it off and never goes to it again. Then I found by cases that every Squared room (i.e. room $1, 4, 9, 16, 25, ..., (1000^2$) remains on). By testing I can see that these are the only rooms that remain on, and there are 1000 of them but I'm not sure how to prove it. I know it has to do with Tau(n) and possibly Sigma(n).

edit: So here is what I came up with, feel free to comment about it:

We establish τ(n) for our question by seeing τ(n) can either be odd or even. By question 2[Let n be a positive integer, prove that n is a perfect square ⇔ τ(n) is odd.], τ(n) is odd ⇔ n is a perfect square, otherwise τ(n) is even. When τ(n) is odd it can be noticed that the room is reached an even number of times since we are disregarding 1 as a divisor. That is, each odd time a room is reached the lights are turned off, and every even time the room is reached the lights are turned on. Moreover, the only rooms that are reached an even number of times are the perfect squares and these are the only rooms that are left on. Then we can see that $1000^2 = 1000000$, and we include this room in our question. We can conclude that rooms $1^2, 2^2, 3^2, … 999^2, 1000^2$ are the only rooms left with the lights on, so there are $1000$ of them.

It really requires a lot of thinking, I hope my logic is correct.

Solution 1:

No need for needlessly complicated solutions.

If $d$ is a divisor of $n$, then $\frac nd$ is also a divisor of $n$. If we pair them, we see that the number of divisors is even, unless there's a divisor $d$ such that $d=\frac nd\Longleftrightarrow d^2=n$, i.e. $n$ is a perfect square. In that case, the number of divisors is odd.

Solution 2:

Back up a step: assume the hotel starts off dark, and that on the first pass every light is turned on. You can easily see that this is the same problem. A light gets switched each time one reaches one of its divisors. A light ends in the off position iff that number is even, since flicking a switch twice nets no change. Which numbers have an odd number of divisors? The perfect squares.