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.