How many lockers are open after 100 passes of toggles

Problem:

There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

Solution:

To remain open in the end, the locker must be toggled odd number of times.

You can figure out that for any given lock, say lock #42, you will toggle it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the lock, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close.
For every pair of divisors the lock will just end up back in its initial state. so you might think that every lock will end up closed?

Well what about lock #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only toggle lock #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square locks will be open at the end.

So, how many perfect numbers are there from 1 to 100? 10 of them. Therefore, after the 100th pass, we will have 10 lockers open.

Answer:

                   10