Summary: There are 500 doors numbered 1, 2, ..., 500. All doors are closed initially. In iteration k, we toggle the states of doors k, 2k, ..., floor(500/k) * k where k runs from 1 to 500, inclusive. What doors are open in the end?
Only perfect squares have odd number of factors. All other natural numbers have even number of factors. Therefore, only the doors with perfect square numbers on them get toggled odd number of times and end up in states that are opposite of their initial states.
> The summary description matches the current correct code. So it could not possibly match any incorrect code.
Incorrect. Here's the summary reproduced (in case susam edits again):
>>> There are 500 doors numbered 1, 2, ..., 500. All doors are closed initially. In iteration k, we toggle the states of doors k, 2k, ..., floor(500/k) * k where k runs from 1 to 500
Note the "floor(500/k)" statement. That matched the original code fragment (and what is still sitting in a terminal on my laptop):
>>> [k**2 for k in range(1, int(500**0.5))]
but not the new one which includes a +1. int(…) is floor. int(…)+1 isn't, and it's wrong: It works for 500, but not for other values. math.ceil would have been more correct, but it might've been more obvious that it doesn't match the "summary".
> (if it really existed).
Let me make sure I understand what you mean here: You actually think it more likely that my two implementations, written in a comment [1] with a lower timestamp than [2], and the perl6 implementation on the linked article all include 484 as part of the valid result, and yet my comment [2] that calls on this value specifically, was somehow meant to indicate that 484 is not part of the valid result?
The +1 makes the range inclusive rather than exclusive. This matches the summary, which is inclusive of floor(500/k). Ceil wouldn't correctly handle the case where the number of rooms equals a perfect square. That is,
Only perfect squares have odd number of factors. All other natural numbers have even number of factors. Therefore, only the doors with perfect square numbers on them get toggled odd number of times and end up in states that are opposite of their initial states.
Python solution: