Is my answer to this math riddle correct, and is there an easier method of solving it?

Question

I've been given the following riddle by my boss, and while I think I might have figured out the answer, I'm not entirely sure how to check that it's correct since I kind of cheated and wrote a python script to do it the long way for me.

The Riddle:

You're in a room with 100 lockers labeled from 1 to 100. A bomb is tripped and the only way to disarm it is to open a specific set of lockers and only that set.

The process to figure out the set is:

1. Open all the lockers
2. Close every second locker
3. Switch the state (open/closed) of every third locker
4. Switch the state of every 4th locker
5. Switch the state of every 5th locker
6. Repeat until the 100th locker

Which lockers must be opened to diffuse the bomb?

You have no time limit, but the bomb is wired to blow by the 10th iteration.

As you can tell I've ignored the last instruction in favor of just figuring out which damn doors need to be opened, so I assume there has to be a much easier way to do it.

This is what my script is spitting out at the moment:

'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'CLOSED', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN', 'OPEN'

And this is the actual script in case anyone wanted to look at it:

arraycounter = 0
statearray = [] #array of door states

#Set all doors to 'open'
while arraycounter <= 99:
    statearray.append(1)
    arraycounter = arraycounter + 1

#Reset arraycounter
arraycounter = 0

#Loop through each door in array
while arraycounter <= 99:
    arraycounter = arraycounter + 1 # ?
    counter = 0
    counter = counter + arraycounter

    #Change door states
    while counter <= 99:
        if statearray[counter] == 0: # If door set to closed, set to open
            statearray[counter] = 1
        elif statearray[counter] == 1: # If door set to open, set to closed
            statearray[counter] = 0
        counter = counter + arraycounter # Move on to next item in array

#Beautify output
arraycounter = 0
while arraycounter <= 99:
    if statearray[arraycounter] == 1:
        statearray[arraycounter] = "OPEN"
    elif statearray[arraycounter] == 0:
        statearray[arraycounter] = "CLOSED"
    arraycounter = arraycounter + 1

print statearray

Am I completely wrong? How would I go about solving this without having to write a script?

Answer 1

A locker is switched at stage n when n is a divisor of the locker number. So we have an odd number of swithces, meaning the locker ends up open, when the locker number has an odd number of divisors. Can the asker work out what sort of numbers have an odd number of divisors? Hint: The sixth such number is 36.

JMoravitz mentioned this in the comments and he is, uh, squarely on target.

Answer 2

The doors that get opened have a number $n$ with an odd number of divisors (including the one).

The function that counts divisors is $$ d(n) = \sum_{d\mid n} 1 $$ If the unique prime factorization of $n$ is $$ n = \prod_i p_i^{e_i} \quad (*) $$ then $$ d(n) = \prod_i (e_i + 1) \quad (**) $$ as we can vary each power $e_i'$ of the prime factorization of a divisor $d = \prod p_i^{e_i'}$ between $0$ and $e_i$.

So $d(n)$ is odd for the doors that have to be opened and this means all the factors in $(**)$ need to be odd and thus all $e_i$ in $(**)$ and $(*)$ need to be even.

This means we can take $n^{1/2}=\prod_i p_i^{e_i/2} = \sqrt{n}$ and stay in the integers.