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.

Neal Stephenson

Posted on September 26, 2011 by Steve

It was seven years ago that I snapped, with a CLIÉ, the photo that would become, for a while, the image for Wikipedia's article on Neal Stephenson.

Mr. Stephenson was back in D.C. this week for the National Book Festival, reading from his latest thousand-page tome, this one written not with a fountain pen but using Scrivener.

I was late for the reading but managed to catch the end and get in line for the Q&A session. The audio was a bit clumsy, with large loudspeakers pointed straight at the questioners, causing them to shrink away while Neal struggled to hear. I got the last question in.

mp3
NTS: Okay we're in overtime I'll just take one more real quick.
Q: Thanks, Neal. The word from Venezuelan state television is that Presidente Chavez intends to repatriate eleven billion dollars worth of gold reserves, most of which are now in London.
NTS: I can't hear what you're saying, sorry.
Q: [same volume, one octave higher] From Venezuela, Presidente Chavez intends to repatriate eleven billion dollars worth of gold reserves. Any comments on the logistics of that kind of a transfer?
NTS: I'm not somebody who is really competent to have an opinion about it. Interesting factoid; thanks for mentioning it.
Something makes me think Dubner, asking over a calibrated, burr-ground, skimmed and French-pressed coffee, would have gotten an answer. Commenters on both the news article and a referring blog made Stephenson connections. I'll have to settle for a chuckle from the audience.

I followed the ridiculously slow-moving author cart over to the signing table, thinking I would get one up on the other fans, only to find a hoard of them already queued up. Not content with my goofy question, I planned to present the author with my smartphone, freshly-purchased Kindle version of Cryptonomicon opened to the title page. I even brought a Sharpie in case his fountain pen didn't work on the screen protector. But the line was long, and one of the handlers mentioned that some of the authors are fussy and refuse to sign anything but their current book. I lost my nerve and bailed out.

At least I have a legitimate, searchable copy of a great novel now, so I don't have to rely on that pirate site with its copy of Randy Waterhouse's treatise on the challenges of massive international gold transfer.