Hacker News Reader

Comment by gct | Hacker News Reader

He said the perfect squares are the only ones with an odd number of factors, which doesn't make sense to me. 16 for example has 4, 25 has 5, 36 has 4 again, so I'm not sure what he was getting at.

View on HN

One easy way to see this: if d is a factor of n, then n/d is a factor of n (since d divides n evenly). So, for any integer, we have pairs of factors (d and n/d) and thus an even number of factors, except in the case when d and n/d are the same.

When are they the same? When d = n/d, or d^2 = n (n is a perfect square). Therefore, only perfect squares have an odd number of factors (2 * the number of pairs of factors + 1).

The first door will only be flipped once, by the first person. The fourth door will be flipped by the first, second, and fourth people (three times). The ninth door will be flipped by the first, third, and ninth people (three times). The sixteenth door will be flipped by the first, second, fourth, eighth, and sixteenth people (five times). The twenty-fifth door will be flipped by the first, fifth, and twenty-fifth people (three times). The thirty-sixth door will be flipped by the first, second, third, fourth, sixth, ninth, twelfth, eighteenth, and thirty-sixth people (nine times).

It should be clear here that the number of times the nth door is flipped is the number of unique divisors that n has.

For any non-perfect square n, for any divisor p, n/p = q is another divisor not equal to p. So non-perfect square numbers have an even number of divisors.

Perfect square numbers are the only numbers that have an odd number of divisors, which in this game corresponds to being flipped an odd number of times.

You could take this a step further. For any number of lockers/kids, if you start at 1 and square each number until you get a number that exceeds the number of lockers/kids, you've found all of your perfect squares in that range. Which, of course, is the square root of your original number, rounded down to the nearest whole number.

So, for any number of lockers/kids, n, the number of open doors is simply floor(sqrt(n)).

16: 1 2 4 8 16 (5)

25: 1 5 25 (3)

36: 1 2 3 4 6 9 12 18 36 (9)

So is this the right answer?

Yes. Not too hard to confirm with a tiny little program:

    lockers = ['Closed'] * 101
    for i in range(1, 101):
      for locker in range(i, 101, i):
        lockers[locker] = 'Open' if lockers[locker] == 'Closed' else 'Closed'

    print ([locker for locker, value in enumerate(lockers) if value == 'Open'])

    >>> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Reply on news.ycombinator.com