Hundred-Dollar, Hundred-Digit Challenge Problems

The hundred-dollar, hundred-digits challenge problems are a set of ten problems in numerical analysis published in the January/February 2002 issue of SIAM News (https://www.siam.org/siamnews/01-02/challenge.pdf). 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

(1)

which converges fairly rapidly using oscillatory numerical integration techniques.

Boersma and Jansen used contour integration to transform the problem into

(2)

each of which converge quite rapidly.

Laurie noted that the integral can be written

(3)

where  is any contour from 0 to 1 such that no singularities lie in the region defined by  and the line from 0 to 1 (Wagon 2004). For example,  is such a contour.

The problem can also be solved by writing the integrand as the asymptotic series

(4)

and integrating term by term to obtain the strongly oscillatory sum

(5)

Amazingly, this sum can be regularized using Wynn's epsilon method using a suitable number of terms and extrapolation degree to obtain around 7 correct digits.

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

(6)

i.e., the matrix

(7)

4. What is the global minimum of the function

(8)

(Cf. Bailey et al. 2007, pp. 12 and 219; Kampas and Pintér 2006). This problem can be solved in a one-liner in the Wolfram Language.

  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 solution is given by solving

(9)

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

(10)

where  is the arithmetic-geometric mean.

It is also given by solving , where

			(11)
			(12)
			(13)

(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  digits:

(14)

(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

(15)

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

(16)

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? Amazingly, this problem has a closed-form solution, given by

			(17)
			(18)
			(19)
			(20)

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

The solutions are summarized in the following table.

#	OEIS
1.	A117231	0.3233674316
2.	A117232	0.9952629194
3.	A117233	1.274224152
4.	A117234
5.	A117235	0.2143352345
6.	A117236	0.06191395447
7.	A117237	0.7250783462
8.	A117238	0.4240113870
9.	A117239	0.7859336743
10.	A117240

REFERENCES:

Bailey, D. H. and Borwein, J. M. "Sample Problems of Experimental Mathematics." 22 Sept. 2003. https://crd.lbl.gov/~dhbailey/expmath/expmath-probs.pdf.

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. Experimental Mathematics in Action. Wellesley, MA: A K Peters, 2007.

Beard, B. B.; Medley, B.; and van Gans, M. "The 2002 SIAM Challenge." https://www.maxwellian.demon.co.uk/~marijke/SIAM2002/.

Boersma, J.; Jansen, J.; Simons, S.; and Steutel, F. "The SIAM 100-Dollar 100-Digit Challenge." https://www.win.tue.nl/scg/siamcontest/.

Bornemann, F. "Short Remarks on the Solution of Trefethen's Hundred-Digit Challenge." Nov. 5, 2002. https://www-m3.ma.tum.de/m3old/ftp/Bornemann/pdf/short.pdf.

Bornemann, F.; Lauire, D.; Wagon, S.; and Waldvogel, J. The SIAM 100-Digit Challenge: A Study in High-Accuracy Numerical Computing. Philadelphia, PA: SIAM, 2004. Additional material available at https://www-m8.ma.tum.de/m3/bornemann/challengebook/.

Borwein, J. M. "The 100 Digit Challenge: An Extended Review." Math. Intelligencer 27, 40-48, 2005.

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 22-24, 2003.

Briggs, K. "Hundred-Dollar, Hundred-Digit Challenge." https://keithbriggs.info/solutions.html.

Kampas, F. J. and Pintér, J. D. "Configuration Analysis and Design Using Optimization Tools in Mathematica." Mathematica J. 10, 128-154, 2006.

Kern, M. "Solution to the SIAM 'Hundred-Dollar, Hundred-Digit Challenge'." Report. May 2002. https://www-rocq.inria.fr/~kern/Challenge/RR-challenge.pdf.

Laurie, D. "Trefethen Challenge Problems." https://dip.sun.ac.za/~laurie/trefethen-challenge/.

Leslie, M. (Ed.). "NetWatch: Decimal Decathlon." Science 295, 1431, 2002.

Sloane, N. J. A. Sequences A117231, A117232, A117233, A117234, A117235, A117236, A117237, A117238, A117239, and A117240 in "The On-Line Encyclopedia of Integer Sequences."

Trefethen, N. "A Hundred-Dollar, Hundred-Digit Challenge." SIAM News 35, No. 1, Jan./Feb. 2002. https://www.siam.org/siamnews/01-02/challenge.pdf.

Trefethen, N. "The SIAM 100-Dollar, 100-Digit Challenge." https://web.comlab.ox.ac.uk/oucl/work/nick.trefethen/hundred.html.

Trefethen, N. L. "Chastened Challenge Sponsor: "I Misjudged." SIAM News 35, No. 6, 1-3, July/Aug. 2002.

Trott, M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, p. 109, 2004. https://www.mathematicaguidebooks.org/.

Weisstein, E. W. "A Hundred-Dollar Challenge." MathWorld Headline News, Feb. 4, 2002. https://mathworld.wolfram.com/news/2002-02-04/challenge/.

Weisstein, E. W. "Hundred-Dollar Challenge Winners Announced." MathWorld Headline News, May 25, 2002. https://mathworld.wolfram.com/news/2002-05-25/challenge/.

Wagon, S. "Solutions." https://stanwagon.com/wagon/Misc/Links/SIAMchallenge_lnk_2.html.

Wagon, S. "The SIAM 100-Digit Challenge." Wolfram Technology Conference, Champaign IL, 2004. https://library.wolfram.com/infocenter/Conferences/5353/.