Re:Is the room open?
by seanhunter on Tuesday February 11, 2020 @02:27AM
(#22296735)
What about 27? It has an odd number of factors but isn't a perfect square.
I think your reasoning fails for x^y where y is an odd number > 1.
The factors of 27 are 1,3,9 and 27. That’s four factors. That's why door 27 is closed at the end of the open/closing process - employees 1,3,9 and 27 touch the door and so the final state of the door is the same as the initial state of the door.
Maybe you are talking about the number of prime factors. This quantity is irrelevant to door open/closing problem.
Re:Is the room open?
by seanhunter on Thursday February 13, 2020 @07:09AM
(#22317090)
Aah you're right. Thanks.
perfect square => even number of factors
n = r^2
n = (p1^k1 * p2^k2 * ... * pi^ki)^2
n = p1^(2 * k1) * p2^(2 * k2) * ... * pi^(2 * ki)
hence n has 2 * (k1+k2+...+ki) factors. Or am I wrong?
Reciprocal left as an exercise ;)
Not really sure what your argument is. But it’s wrong, because n=4 is a counterexample. The factors are 1,2 and 4. This is an odd number of factors.
Edit: it seems you are talking about 'The number of factors in the prime factorization of n'. This is not really relevant to the question posed in the submission.
perfect square <=> odd number of factors
Proof: For every divisor d of n, n/d is another, different, divisor. This gives a pairing of all the divisors. The only exception is if n/d = d.
The exceptional case n/d=d only happens when n=d^2, i.e. when n is a perfect square.
Thus, when n is not a perfect square, there is a pairing of all its divisors, hence the number of divisors is even.
If n is a perfect square, the pairing pairs up all the divisors except for sqrt(n). Thus the number of divisors is odd.