Project Euler update

Posted on September 26, 2011 by Steve

I was made to learn by heart: ‘The square of the sum of two numbers is equal to the sum of their squares increased by twice their product.’ I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way.
--Bertrand Russell
Paul Lockhart [Erdös 2] is the author of A Mathematician's Lament, the best screed I've read in years. The big idea is that contemporary education is broken, which hardly counts as news. But he quite eloquently demonstrates how the standard curriculum sucks all joy and life out of mathematics, which, he argues, should be taught purely as an art, without any utilitarian justification. What math does anyone learn in high school that has any use in the real world? The common inability to compute change without a calculator is often cited as evidence of woeful innumeracy, but Lockhart suggests that it is an appropriate tool; the real tragedy is that students are never given a chance to wonder about or discover mathematical ideas.

The "Lament" was mentioned in an article about Project Euler. Since discovering the site four years ago, I have been slowly picking off problems, sometimes getting stuck or distracted for months. In April 2010 I decided to stop hunting among the 350+ problems for easy scores and finish off the first 100. By Feburary this year, I had one problem left to reach my target. And I got firmly stuck. One of the early lessons in the project is that the direct approach -- brute force -- is usually too slow to get the job done. But, lacking inspiration, I often try it anyway, hoping for enlightenment. In this case I tried all manner of cheap tricks to get the solution in the minute of computer time promised to be adequate for every problem. Memoization, switching in my main loop based on the final two or three digits of the current value, precalculating magic numbers, all to no avail. Working off and on, with many false starts, I eventually accumulated 650 lines of mostly green C code.

Lockhart's screed gave me a critical, and purely psychological, boost. Soon after reading it I had a penetrating insight into the pattern of the problem -- as usual completely simple and obvious in retrospect. I noodled on some scratch paper (eventually to fill four pages) and worked out some patterns. It was a simple matter to put the new approach to code -- but it didn't work. The thrill and hope led to crushing disappointment -- was I perhaps going down one of the same wrong paths I had tried months earlier? Over several days, I repeated this same pattern -- insight, hope, experiment, crushing failure, renewed insight. I recall from Intro to Psychology that the variable positive reinforcement schedule is one of the most effective ways to make the rat keep pressing the lever, and I lost sleep working on the problem.

Finally, I cracked it. A little bit of insight, but mostly recognizing (yet again) idiotic errors in my algorithm led me to the solution (runtime 0.131 sec). I haven't submitted it yet, but I am completely confident. After posting this I will enter my solution and should get a new "award" on the recently-redesigned site: the Centurion is given to those who solve 100 consecutive problems. (Rather an elite group, with only 276 members so far, hopefully 277 soon!)
If there is anything like a unifying aesthetic principle in mathematics, it is this: simple is beautiful. Mathematicians enjoy thinking about the simplest possible things, and the simplest possible things are imaginary.

« Prev item • Next item »

Comments

Posted by RWH | September 27, 2011 | 09:07:44

are you now a centurion steve.

are you.

I want to be a centurion. I have been inspired.

Oh, cute. Logging in for the first time in ages, I see that I have four awards already:

* Decathlete
* As Easy As Pi
* Baby Steps
* The Journey Begins

------------------

Posted by Steve | September 27, 2011 | 14:15:27

There are over 300 Centurions now. I recieved those four baubles and also retroactively merited the Daring Dozen (joining 737 others) and Pythagorean Triplet (687) awards.
------------------

Posted by Steve | October 14, 2011 | 14:30:39

It turns out that Centurions are constantly being added as qualifying members log in for the first time since the awards were introduced. There are over 500 now.

There was a postscript to my story. After posting it, I went to the site and with "complete confidence" submitted my solution. It was wrong.

After an interlude of anguish, mingled with a tiny bit of wonder and joy that there must be something really interesting going on, I went back to RTFP and found that I merely submitted the wrong variable from my correct solution.
------------------

Leave comment

You must be logged in as a member to add comment to this blog