Saturday, February 18, 2012

Euclid stole my thunder

I've often said that my learning style is "learn the system or rules, and then I can figure out everything else later", as opposed to some people who memorize specific results or even specific formulae. (I think the only specific thing I remember from any math class ever is an acronym "FOIL" for multiplying binomials.)

Today is an example of just how true that is, although it also makes me think that perhaps I could save myself some time by memorizing *some* formulae...

I decided [for reasons that are not relevant here] to pick a random problem from Project Euler to solve. The problem I happened to choose was #5... go check it out, I'll wait.

Starting from a blank slate, working through it in my head and writing code in C# (part of my goal was to solve it in a way that is computationally efficient), I figured out the solution. Partway through I realized that I was re-deriving basic things like "how to find the least common multiple of two numbers", and as part of that "how to find the greatest common divisor of two numbers" ... isn't that elementary school stuff?

Afterwards, I went and looked up these things to see how my results compared. On the plus side, my results are good. On the minus side, I'm 2300+ years behind the curve on being first-to-press with the Euclidean algorithm. But it only took a few hours, why did the Greeks make such a big deal of this? It isn't hard :P

Note: If you feel like commenting on this post, and you also happened to have felt like solving the problem yourself, please do not post your answer. I'd hate to end up as a cheater's search result for people who are working on the Euler problem.

Addendum to note: heh. Go search for some web calc that does least common multiples for number sets -- I tried one and it got the question wrong :) It told me "18044195" .. c'mon guys, that is not even an even number! Try harder! And use unsigned long integers in your code!