Out of the wilderness

This morning I finished reviewing and responding to my MATH 461 class's homework set, the one featuring several very open-ended problems related to Fibonacci sequences, Euclid's Algorithm, and greatest common divisors. Their work was fantastic, and the sense I got from most students' solutions was that they'd achieved genuine understanding, something I honestly don't see present in most responses to the cut-and-dried prove-this-theorem sorts of questions one might ask in an upper-level mathematics course.

Moreover, the students made remarkable progress in proving some nontrivial mathematical results they themselves got to formulate. Several presented solid proofs of one direction of the equivalence I mentioned in my last post, and though no one successfully proved the converse (I was only able to do it myself last night, after several false starts), a few students made earnest attempts at so doing and a few finished just shy of the mark.

Furthermore, two of the students noticed that, though I'd not intended it, the fourth problem on the homework set had close ties to the previous three (all of which were similar). This last problem asked them to characterize the numbers which caused "worst-case" performance in Euclid's Algorithm when divided into 99. A bit of thought (after examining a mess of data) will convince you that the worst case is achieved when the numbers you select give the most "Fibonacci-like" sequence of quotients when divided into 99, numbers for which most of the "q" values stemming from Euclid's Algorithm are 1, so that the corresponding remainders remain as large as possible. Thus, these two students pointed out, Euclid's Algorithm should perform most poorly when you use to divide one Fibonacci term into its successor. One student even presented several pages of numerical evidence for this worst-case behavior, building off of the generalized Fibonacci sequences we'd just worked with above. It was splendid.

Finally, one student made an observation regarding the frequencies with which each "run time" occurred when Euclid's Algorithm is applied, noting that when plotted, these frequencies traced out a very normal-looking curve. "What might happen with other values for b, besides 99?" he asked. No doubt there's some nontrivial number theory lurking just below the surface: primality plays a role, for sure, and I'm sure Euler's φ comes into play.

All in all, I get the feeling that the students got far more out of this set of exercises than most (any?) I've ever assigned in my career. I'm going to see that all of my homework sets for the rest of the semester are in a similar vein.