I’ll take it to mean, “given a number, N, can you tell me if that light will be on or off?” They’re not looking for a proportion or anything like that.
Anyway. . .the easy part: first of all, you know that any prime number will be ON.
Seems to me you need to know the NUMBER of divisors each number has. If that’s ODD (including itself, like 15: 3, 5, 15 or 6: 2,3,6) then the light will be ON. If that’s EVEN (like 16: 2, 4, 8, 16 or 49: 7,49) then the light will be off.
But, I don’t know an easy way to find the number of divisors of a number.
Any thoughts? A simple trick that I’m overlooking?
Unless I’m mistaken, at the point at which someone comes along and pulls every 20,000th chain, all the Prime numbers less than 20,000 will be OFF, not ON. Someone turned them all on initially.
For instance, 7 is a prime number. It was originally ON (after dude #1 pulled all the cords), and was turned off when dude #7 came through and pulled every 7th chain.
Actually, it’s a bit simpler than you think: All the lights will be off except those lights that are perfect squares. Remember all divisors come in pairs, so each pair (even the 1,N pair) will represent an ON and and OFF. The only exception is the perfect square, which, since the square pair consists of identical numbers, gets an odd number of pulls.
Aren’t the only numbers with an odd number of factors the squares? Just off the top of my head, it seems like any other number is going to have pairs of factors:
Since each factor of a number must be multiplied by another different factor (call them partners), they’re always going to be in pairs except for the special case where the factor is its own partner.
So I posit that
(1) if all of the bulbs start out OFF
and
(2) if the first walk through the hall dispatches the responsibility for the “1” which is every number’s factor
then
on the Nth switch-flipping, all of the squares lower than N will be ON and every other bulb will be OFF.