Hundred-Dollar, Hundred-Digit Challenge Problems

The hundred-dollar, hundred-digit challenge problems are a set of ten problems in numerical analysis published in the January/February 2002 issue of SIAM News (Trefethen 2002). Nick Trefethen, the proposer of the problems, offered a $100 prize to the person or group obtaining the largest number of correct digits (up to a maximum of 10) for these problems by May 20, 2002. Trefethen underestimated the ingenuity of problem solvers, and 20 independent teams obtained 10 correct digits for all 10 problems. After an anonymous donor stepped in to help defray the larger than anticipated payoffs, prize checks went out to all winners by December 2002.

The problems posed were the following.

1. What is ? This problem is difficult to integrate numerically in its original form because of the strong oscillations near the origin. However, by making the substitution , it can be transformed to the integral

where is the principal branch of the Lambert W-function. This integral can be evaluated using oscillatory numerical integration techniques.

Boersma and Jansen used contour integration to transform the problem into

both of which converge quite rapidly.

Laurie noted that the integral can be written

where is the piecewise linear contour from 0 through to 1 and the complex exponentiation uses the principal branch of the logarithm (Wagon 2004).

The Taylor series of is

for . Formally integrating its terms against over the positive real axis leads to the divergent series

Its terms do not tend to zero, so it does not converge as an ordinary series. Wynn's epsilon method can be applied to its finite partial sums.

2. A photon moving at speed 1 in the - plane starts at at heading due east. Around every integer lattice point in the plane, a circular mirror of radius has been erected. How far from the origin is the photon at ?

3. The infinite matrix with entries , , , , , , etc., is a bounded operator on . What is ? This problem is equivalent to finding the largest singular value of the infinite matrix with entries

i.e., the matrix

4. What is the global minimum of the function

(Cf. Bailey et al. 2007, pp. 12 and 219; Kampas and Pintér 2006). A numerical candidate for the global minimum can be computed in the Wolfram Language, with the objective above. This numerical search does not prove that the candidate is the global minimum.

  NMinimize[f[x, y], {x, y}, Method -> {"RandomSearch",
    "SearchPoints" -> 700}, WorkingPrecision -> 20]

5. Let , where is the gamma function, and let be the cubic polynomial that best approximates on the unit disk in the supremum norm . What is ?

6. A flea starts at on the infinite two-dimensional integer lattice and executes a biased random walk: At each step it hops north or south with probability 1/4, east with probability , and west with probability . The probability that the flea returns to (0, 0) sometime during its wanderings is 1/2. What is ?

The positive solution, with , is given by solving

where is a complete elliptic integral of the first kind. Equivalently, it is given by the root of

where is the arithmetic-geometric mean.

It is also given by solving , where

(Bornemann 2002).

7. Let be the matrix whose entries are zero everywhere except for the primes 2, 3, 5, 7, ..., 224737 along the main diagonal and the number 1 in all the positions with , 2, 4, 8, ..., 16384. What is the (1, 1) entry of ?

This problem can be solved exactly, yielding a rational number in which the numerator and denominator each have 97389 digits:

(Wagon 2004).

8. A square plate is at temperature . At time , the temperature is increased to along one of the four sides while being held at along the other three sides, and heat then flows into the plate according to . When does the temperature reach at the center of the plate?

An expression that gives 10 correct digits is given by

where is a polynomial root. Getting higher accuracy requires using more terms of the series.

9. The integral depends on the parameter . What is the value at which achieves its maximum?

By making the change of variables , the integral can be transformed to

Here, is a Meijer G-function. By plotting, the maximum can be seen to occur near , and standard root-finding techniques can be used to determine it to high-precision.

10. A particle at the center of a rectangle undergoes Brownian motion (i.e., 2D random walk with infinitesimal step lengths) till it hits the boundary. What is the probability that it hits at one of the ends rather than at one of the sides? This problem has a closed-form solution, given by

where is the elliptic lambda function (cf. Bailey et al. 2007, p. 48).

The solutions are summarized in the following table.