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.

Geometri sorular

Posted on April 13, 2009 by Steve

This problem appeared in the Science and Technology section of Cumhuriyet on Friday, 10 April 2009 (click image for the question). I confess I wasn't able to solve this problem unaided; I had to look up le théorème d'Al-Kashi. (Jamshid al-Kashi gets a mention in the article on approximations of pi for having derived, in 1424, 9 digits of 2π in base 60.)


Posted on December 17, 2008 by Steve

Ulam lapsed into a coma. His wife, his doctors and his friends worried about brain damage. When he awoke a few days later, Ulam worried about it even more. "One morning the surgeon asked me what 13 plus 8 were. The fact that he asked such a question embarrassed me so much that I just shook my head. Then he asked what the square root of twenty was, and I replied: about 4.4. He kept silent, then I asked, 'Isn't it?' I remember Dr. Rainey laughing, visibly relieved, and saying, 'I don't know.'"
Richard Rhodes, Dark Sun

Sex in C++

Posted on May 02, 2008 by Steve

Some time ago I was clicking around Wikipedia's content on artificial intelligence and encountered the article on genetic algorithms, and decided I would use one to solve a Project Euler problem. The first task was to find a suitable problem. To be amenible to a genetic algorithm, the problem should have certain characteristics:

  • It must be possible to rate candidate solutions, with the correct solution getting the highest possible score, and incorrect candidates scoring higher if they are somehow closer to the solution. (Most AI problems, like analyzing chess positions, do not have a single correct answer, so the highest-scoring candidate found in a certain time would be the result.)

  • A candidate solution should be expressable as a series of values, something like a chromosome. It helps if all candidates have the same length and format, so the individual parts are easily interchangeable.

Read on for specific information about my algorithm for Problem #61, including spoilers if you're inclined to try this approach yourself.

Resize problem

Posted on April 24, 2008 by Steve

I downloaded an image having size 1920x1440 that I wanted to use as a desktop. My screen resolution is 1680x1050. To get the aspect ratio right (1.6:1), I cropped the original to 1920x1200 using MS Paint. I then wanted to shrink the image down to fit my desktop, but the resize tool would accept only whole numbers, and I needed to use a factor of 87.5%. I couldn't abide strips on the sides if the result was too small, or the thought that some image would be cut off the edges, or, worst of all, distortion in the image due to a crummy stretch-to-fit.

Some distortion is inevitable in a resize, so I resolved to get my target image size with the minimum number of resizes. How did I do it?

Age and wisdom

Posted on March 18, 2008 by Steve

REM Rootfinder Program
REM Finds Roots using Newton-Raphson method of equation
REM f(x) = 9.34 - 21.97x + 16.3x^2 - 3.704x^3

PRINT "Use Rootfinder to locate roots of equation"
PRINT "f(x) = 9.34 - 21.97x + 16.3x^2 - 3.704x^3"
INPUT "Initial Guess: ", x
INPUT "Stopping Criterion (% Relative Error): ", EC

ITER = 0
ET = 1 + EC
DEF FNG (x) = x - (9.34 - 21.97 * x + 16.3 * x ^ 2 - 3.704 * x ^ 3) / (-21.97 + 32.6 * x - 11.112 * x ^ 2)

WHILE (ET > EC) AND (I < 100)
Y = FNG(x)
IF (Y <> 0) THEN ET = ABS((Y - x) / Y) * 100
PRINT "Iteration: "; ITER, "Estimate: " Y, "Error: "; ET
x = Y

PRINT "Function value at last iteration:"
PRINT "x = "; x; ", f(x) = "; 9.34 - 21.97 * x + 16.3 * x ^ 2 - 3.704 * x ^ 3

This was a homework assignment for my Numerical Methods class dated 8 April 1993. I found the dot-matrix printout while sorting through papers in the basement. The professor wasn't too impressed; he gave me a score of 50/75. He didn't catch the undeclared variable I in the WHILE condition, but circled "IF (Y <> 0)" and wrote "Can you explain what is being checked here?" Seems clear to me, though an ELSE statement would have been a nice touch. He also scribbled "Try both stopping criteria?" and, after checking my result of 0.9535033 in 7 iterations, asked "largest root?" (it wasn't).

One reason I held on to a bunch of school papers was so I could test myself to see if I would gradually get stupider after completing my formal education. I am happy to report that there has not been a precipitous decline. In the copy of the PSAT test that I saved from high school, I couldn't find a single problem in the math section that was hard enough to merit being worked out. Meanwhile, I recently solved my 100th problem on Project Euler, and hope to knock off a few more before dementia sets in.

Project Euler

Posted on September 17, 2007 by Steve

It is positively cheering to see that tens of thousands of man-hours (and undoubtedly some number of woman-hours) are being invested in Project Euler. I have solved five of the easiest problems so far, and am pleased to report that all of my programs run in less than the minute said to be sufficient. Writing the programs is another matter; I didn't expect to find so much challenge and subtlety in writing a simple prime number validator.

I am using this as an exercise to learn some Python in addition to sharpening my number theory; other people take a more traditional approach.

Mitch Feigenbaum

Posted on August 21, 2007 by Steve

From Chaos:

In the spring of 1976 he entered a mode of existence more intense than any he had lived through. He would concentrate as if in a trance, programming furiously, scribbling with his pencil, programming again. He could not call C division for help, because that would mean signing off the computer to use the telephone, and reconnection was chancy. He could not stop for more than five minutes' thought, because the computer would automatically disconnect his line. Every so often the computer would go down anyway, leaving him shaking with adrenaline. He worked for two months without pause. His functional day was twenty-two hours. He would try to go to sleep in a kind of buzz, and awaken two hours later with his thoughts exactly where he had left them. His diet was strictly coffee. (Even when healthy and at peace, Feigenbaum subsisted exclusively on the reddest possible meat, coffee, and red wine. His friends speculated that he must be getting his vitamins from cigarettes.)
In the end, a doctor called it off. He prescribed a modest regimen of Valium and an enforced vacation. But by then Feigenbaum had created a universal theory.

This quote still comes to mind on the rare occasions when I am both busy and doing something I enjoy. I read the book in college, where my idea of keeping busy was to stay up late coding QBasic on a computer that I had obtained in trade for large bag of pistachios. I tried to write a Mandelbrot Set generator, but had to wait until the evening of the following day for enough to be rendered to show that my algorithm was faulty. Eventually, I got it working in Visual Basic.