FORTH GO

After fanatically solving 160+ Project Euler math/programming problems whenever the came out, I’ve accepted an invitation to be part of the testing team. I’ve always thought the problems were very high quality regarding clarity and scale, and now I can confirm that those attributes are quite deliberate based on the discussions I’ve seen leading up to problem publication.

The “one minute rule” is well known at the site and is a requirement that any problem be solvable in under a minute of computation time on a midrange computer. Another rule is that integers larger than 64 bits not be required for the solution; some of my solutions have needed BigInteger, but I guess I missed some optimizations.

One downside to seeing the problems before they are published is that I can’t compete with the few testers who try to be the first to solve each problem as it comes out. That’s OK with me, and besides I don’t see all the problems ahead of time. There are two separate testing teams, so I can compete on some problems if the timing is right.

The 2008 Science Blogging Conference is coming up January 19. I attended last year and will be co-leading a session this year on “Public Scientific Data”. My selfish interest in public data is wanting to try to improve the visualizations I see in science papers, but I can’t readily do it without the data. The other discussion leader, Jean-Claude Bradley, is a real scientist, though, running a real open science chemistry lab at Drexel.

I started a skeleton outline of some of the issues at the conference wiki, and I’m happy to see others have expanded it.

Problem 156 at Project Euler is one of the few without a specified limit. That is, most problems might ask for something like the sum of all solutions to an equation that are less than a billion. This one just asked for the sum of all solutions. When I first solved it, I just used the sum of solutions up to a trillion, which was good enough. Later I made some plots to help understand why there are no higher solutions.

Mild spoilers below if you’re thinking about trying the problem.

The problem is to find the solutions to f(x) = x where f(x) is the number of times a given digit, say 4, appears in all the numerals corresponding to the numbers from 1 to x. The equivalent problem is to find where f(x) - x = 0. The plots below show f(x) - x at different scales.

The first scale suggests f(x) - x for the whole range I looked at.

The second scale shows where the function really takes off and why. For each 1e10 range there seems to be about as many 4s as numbers (the function keeps dipping to around 0) until it gets to 4e10 when each new number in the 4e10 to 5e10 range has at least one 4 and sometimes more, so the function really takes off, especially at 4.4e10.

Zooming in more shows a fractal-like nature to the function.

The varying density of the points is because my implementation makes fewer evaluations when further away from the origin.

This is a heat map graph of a mathematically generated data set with a little noise added for artistic effect. Next year I’ll work on anti-aliasing the edges.

Project Euler hosts a growing collection of math programming problems that I started participating in earlier this year while it was on the mathschallenge.net web site. Typically, you have to write a program to solve a math problem and then enter your solution to get credit for it. It took me a couple of months to solve all the existing problems, and since then I’ve been solving new problems as they come out, every few weeks.

There are about 50 participants who solve all the problems as they come out and maintain their status as “100% genius” at the site. Among those, there are about a dozen who compete to solve new problems as quickly as possible since ties in the rankings are broken by time of submission of the solution. New problems always come out on Fridays at 1pm (EST) so I usually don’t get to work on them until the evening, which typically results in a “ranking” of around #15.

This week I was off work for the holidays and delayed our trip up to Hyco Lake for a few hours so I could take a crack at the new problems coming out. There were two new problems this time, involving finding solutions to the same Diophantine equation for certain values of n. In the first problem n was bounded to 1 million, and a simple brute force search worked fine. The second problem allowed n to go to 50 million. I started a similar brute force search running just in case it finished, though I knew there must be a simpler solution (all problems are designed to take less than a minute to execute). Being in a hurry, I only did a little analysis and then studied the first hundred or so brute force solutions to find a pattern and guessed that the pattern held for the whole range. It worked, and I ended up in first place on the scores list, at least until the next problem comes out.

Later, I let the brute force attack complete, which took about an hour. I also took the time to figure out why the pattern I observed held.

If you look up any math term in Google, you likely get front page links to articles at Wikipedia and MathWorld. Both are usually very good, with the latter being more formal but having a Mathematica slant. (MathWorld is hosted by Wolfram Research, makers of Mathematica).

MathWorld has guest contributors but is otherwise closed content, unlike Wikipedia which is completely open. But as I found out last week, MathWorld does accommodate content suggestions. I completed the comment form twice for the Cuban Primes page, once for a typographical error and once for a factual error. I got a response noting the corrections a few days later. Not quite the turn-around of Wikipedia corrections, but still functional.

I can confirm the errors were fixed, though now I see the last modification time stamp wasn’t updated …

Fermat’s Last Theorem may have already been proved, but the proof is so dense amateurs like myself still foolishly search for a simple proof. My latest foray was centered around a trigonometric mappings.

That is, start with aⁿ + bⁿ = cⁿ, divide through by cⁿ and then map the resulting equation to the trig identity sin² x + cos² x = 1. So (a/c)ⁿ maps to sin² x and (b/c)ⁿ maps to cos² x, which means we need to find an angle x that sin^2/n x and cos^2/n x are both rational. If so, then we can raise them both to the nth power to get the trig identity and multiply through by the Least Common Multiple of the demoninators to get a solution to Fermat’s equation.

So we actually need to prove that sin^2/n x and cos^2/n x cannot be both rational for a given x, except for trivial cases like x = 0. That’s about as far as I got, but the presentation has a nice feature in that it suggests that n = 1 and n = 2 are special since those are the only values when 2/n is an integer. Likewise, they are the only values of n for which Fermat’s equation has non-trivial solutions. Also the trivial solutions to Fermat’s equation, a = 0 and b = 0, correspond nicely to the trivial solutions in the trig representation where x is 0 or Ï€/2.

I tried a Taylor expansion of sin^2/n x and cos^2/n x, but I couldn’t expand them at 0 since the exponents would result divisions in by 0. I expanded around Ï€/4, which has the nice property of sin Ï€/4 = cos Ï€/4 = sqrt(1/2). Still nothing obvious panned out. Simplifying infinite series is not a specialty of mine.

I was hoping to reduce each series to the form U ± V, where at least one of U or V can be proved irrational. In that case, I could prove that U + V and U - V couldn’t both be rational. If both U + V and U - V were rational, then their sum (2U) and their difference (2V) would be rational.