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!


Anonymous said...

Yikes!! I'm sure glad I decided I liked training horses better than doing Math. That stuff makes my head spin. But I'm sure proud that YOU understand it and can do it!
Love you tons!

Talena Winters said...

Elementary school... of course... I'll get Jude working on this right away! :-)

Hey, I solve fiendish garment construction problems... so what right have I to shake my head at what you do for fun? ;-) (But I might be, anyway. Just a little.)

Logan said...

... c'mon, he must be able to at least prime factor a number by this point, right? (ie, reduce 20 to 2x2x5) That is what I meant by elementary school, not "solving Euler problem #5" :)

Or finding the least common multiple of two numbers, which probably comes up in the curriculum when you start to add and subtract fractions (ie, 1/2 + 1/3 = 3/6 + 2/6 = 5/6)

Logan said...

Also for the record, I didn't mean "first day of Grade 1" .. but 6th grade is still elementary school! :P

Talena Winters said...

Pretty sure that prime numbers don't come in until next year or the year after (still elementary, I realize), however, Jude just told me that he has had to add fractions with different denominators this year, so I guess that's a start... :-)