Mathlesstraveled.com Website Review

itself would be silly, since we should just use the simpler GCD test instead! At long last, here is the solution I had in mind for the Wizard’s rational puzzle a secret rational number, if all we are allowed to do is reciprocate, add, subtract, multiply, and compare. Given the exact sequence of operations you did to reduce the rational to zero, you can easily reverse them to reconstruct the original rational. For example, suppose you had to subtract 1 three times, then reciprocate, then subtract 1 five times, reciprocate, then subtract 1 This clearly gives the right answer; the only question is whether it will stop after a finite amount of time. But it does, since every time we subtract 1 we are making the numerator smaller without changing the denominator, and reciprocating just switches the numerator and denominator without making them bigger. Also, if we had a number less than 1 and reciprocate it, the result will definitely be bigger than 1, at which point we can subtract 1 from it at least once, and hence we cannot get stuck reciprocating repeatedly without doing any subtracting. Since we have two positive integers which are either staying the same or getting smaller on each step, the process must There are several equivalent ways to think about what is going on here: Another way to think about it is that we are running the Euclidean Algorithm the gcd of its numerator and denominator will be 1, so finding the gcd doesn’t tell us anything in and of itself. The point is, however, Yet another way, closely related to the previous, is to imagine that we are finding our way up the Calkin-Wilf tree left. Reciprocating corresponds to mirroring the entire tree left-right, and then we can continue taking steps up and to the left. is greater than 0 to see whether we should reciprocate or stop.) On the other hand, the best case takes only two operations (a subtraction and a comparison, if the result is still greater than one). The worst case for a given depth in the C-W tree would be if we start with the