Project Euler and Self-Directed Learning

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Apropos of Tex's recent post on child-centered learning, I thought I'd add this.

Computer programming is a hobby of mine and something I am very interested in getting better at, but I was never good at math. Call me lazy, but the most difficult thing in math classes was keeping my eyes open; after missing the instruction, the problems were often impossible. (If it's impossible, it's not difficult, you see.) The textbooks were even more boring than the teachers, so they were no help, either.

In the last few years I've become increasingly interested in learning more math, but the problem is where to begin and how to approach it. I dread taking university math courses, an expensive cure for insomnia in my experience. Then I read James Somer's article, How I Failed, Failed and Finally Succeeded in Learning How to Code, where he introduces Colin Hughes, a British math teacher and the creator of Project Euler.

The core of Project Euler is a set of math problems designed to be solved by simple computer programs. Currently, there are more than 400 and Mr. Hughes adds a new one each weekend during the school year (he takes summers off). Interestingly, other than a simple explanation like the one above, he provides no instruction in math with the problem, but after you give the correct answer, it opens up a discussion thread for everyone who has solved the problem to share their solutions and comments with each other.

My route to solving these problems has generally been either to just start writing the program, if I immediately grasped the problem (like Problem 2 above), or if I didn't, to look up related math topics on Wikipedia, which has a surprisingly large number of helpful articles. I try to find a principle that will allow me to solve that type of problem (I avoid simply searching for  the problem itself; some unsporting types have posted their solutions publicly). After solving the problem, I go through a dozen or so solutions from others who have also solved it.

Hughes explains his method like this: "The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem."

That seems to be how it's working for me. While the problems have gotten more difficult, I've become quicker to pick up on patterns in numbers and, when I don't understand a problem, I have a better idea of how to approach finding the answer. I've built up a better understanding of how numbers work together, a clearer understanding of some math concepts, an appreciation for different types of math (number theory, graph theory, combinatorics, etc.) and am solving the problems faster. I am, in fact, learning math.

My proudest achievement there so far has been solving problem 15. Wikipedia was entirely useless (I later found out that I was looking in the wrong articles), so I had to sit down with pen and paper and work through simpler versions of the problem until I found a pattern. Then I created my own formula to solve the problem, implemented it, and it worked. It took me nearly a week of spare time. Then I went into the discussion forum for that problem and found two vastly simpler ways to solve it, and of course I got a good laugh out of that. Then it was on to the next problem.

7 comments:

  1. Oh, and for one problem I went and watched several Khan Academy videos.

    ReplyDelete
  2. The Fibonacci sequence is the solution of a difference equation with constant coefficents. Any such equation can be explicitly solved. If one has any sequence satisfying a difference equation with constant coefficents then the sequence formed by summation of the first n terms also satisfies a difference equation with constant coefficents. Since the starting sequence is obtained by differencing the sequence formed by summation one has only to substitute the difference operator in the difference equation for the original sequence to obtain the difference equation for the sequence formed by summation. Then an explicit formula for the sums is readily found. A similar technique can be used to explicitly integrate any function satisfying a differential equation with constant coefficents.
    These techniques have been known since at least the eighteenth century.
    Finding the sum of the even-valued terms is an artifical problem of no interest whatever.

    ReplyDelete
  3. When referring to difference and differential equations in the above post I mean linear difference an differential equations.

    ReplyDelete
  4. A problem of no interest whatsoever? Interest truly is in the eye of the beholder.

    ReplyDelete
  5. Finding the sum is not the point, in any case. The point is learning the finer points of how to use code to capture the solution.

    I learned to code some years ago, when I was in college and had loads of time on my hands. We used to build all kinds of things -- weather simulators, ship simulators, tons of stuff. You'd start by thinking, "What would really be nice is to have a code that would tell me the exact phase of the moon at any time," and then you'd start thinking about how you'd make that work.

    ReplyDelete
  6. Dammit, Jim! It's education, not research!

    Scotty! The captain's blood-context level is low -- beam him up!

    ReplyDelete
  7. Grim,

    Sounds pretty cool. I'm hoping to learn enough to make some games I have in mind.

    ReplyDelete