Hacker News Reader

Comment by susam | Hacker News Reader

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.

Python solution:

  >>> [k**2 for k in range(1, int(500**0.5) + 1)]
  [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484]

View on HN

That's incorrect. Room 484 stays open.

Edit: I see you've updated your code susam.

484 is a perfect square. (22×22)

Edit: I see you've updated your comment geocar.

484 wasn't returned by the code susam originally posted.

Isn’t it funny how a python one liner required two edits to produce the correct result? (The summary description still matches the old incorrect code)

> The summary description still matches the old incorrect code

The summary description matches the current correct code. So it could not possibly match any incorrect code (if it really existed).

> 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?

Ha.

[1]: https://news.ycombinator.com/item?id=22288534

[2]: https://news.ycombinator.com/item?id=22288554

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,

  [k**2 for k in range(1, ceil(484**0.5))]

does not return 484.

Quite right! So a 1+ is needed.

I can't amend my comment to that point, but the original comment didn't have +1 in there anyway.

Reply on news.ycombinator.com