Quick! What do the numbers 5, 6, 7, 13, 14, 15, 20, 21, 22, and 23 have in common? If you said they're all "congruent" numbers--numbers related to the areas of certain triangles--then you may be one of those folks who scored an 800 on your math SAT. Even if that answer didn't leap to mind, you may be intrigued to know that mathematicians have now cataloged the congruent numbers--which are easy to define but not so easy to spot--up to a trillion.
A congruent number is simply a whole number like 1, 2, 3, ... that happens to be the area of a right triangle (one with a 90-degree corner) whose three sides all have lengths that are either whole numbers or fractions like 3/2, 10/3, ... For example, 6 is a congruent number, because it's the area of the familiar 3-4-5 right triangle. So is 5, because it's the area of the right triangle with sides of length 3/2, 20/3, and 41/6.
Oddly enough, even though congruent numbers are easy to define, spotting them or even estimating how many there are isn't so simple. Ask any mathematician how many prime numbers--numbers divisible only by themselves and 1--there are up to a zillion, and they snap back with an approximation: about a zillion divided by the logarithm of a zillion. Mathematicians have no similar approximation for the number of congruent numbers.
That may be about to change. An international group of computational number theorists has completed a systematic survey of "candidate" congruent numbers up to a trillion, extending earlier work that had stopped at a billion. This survey builds on a 1983 breakthrough by Jerrold Tunnell, now at Rutgers University, New Brunswick. Tunnell found a way of identifying such numbers with straightforward but brute-force calculation. More specifically, he showed that all these candidates are indeed congruent numbers, provided that a widely believed claim known as the Birch and Swinnerton-Dyer conjecture--one of seven "million-dollar" prize problems posed by the Clay Math Institute--is true.
In essence, Tunnell's approach finds all such numbers up to some number N by expanding a polynomial of degree N. That's easy enough when N is small, like 10 or 20 or even 1000, but computationally demanding when N gets into the billions. To expand the search 1000-fold, two teams did the calculation using two different algorithms on two different computers. William Hart of the University of Warwick in the United Kingdom and Gonzalo Tornaria of the Universidad de la República in Uruguay ran one calculation; Mark Watkins of the University of Sydney in Australia, David Harvey of the Courant Institute of Mathematical Sciences at New York University, and Robert Bradshaw of the University of Washington, Seattle, ran the other.
Both calculations used a staple in large-scale scientific computation known as the Fast Fourier Transform, adapted for number theory. In general, the transform streamlines otherwise unwieldy computations by systematically partitioning the data. It has been used, for example, in computing the first trillion digits of pi. For technical reasons, the researchers didn't bother counting all candidate congruent numbers, just ones in a subclass consisting of "nontrivial" cases, as they explain in a preprint posted on the Web site of the American Institute of Mathematics. Their computations agreed that, up to a trillion, this subclass contains exactly 3,148,379,694 candidates.
The results, the researchers say, will help discriminate between some competing guesses for formulas that predict the number of congruent numbers. Moreover, the computational techniques they developed should prove useful for a variety of other number-theoretic problems or any computation requiring the exact handling of numbers so huge they cannot fit into a computer's main memory.
The calculations are a "tour de force," says Tunnell, who started it all. "I did not envision such extensive computations since naive methods would be a million times slower."