Some simple expressions can generate a surprisingly large number of primes, whole numbers that are evenly divisible only by themselves and 1. The remarkable formula x2 + x + 41, for example, yields an unbroken string of 40 primes, starting at x = 0.
Another simple, prime-rich formula, x2 + x + 17, generates prime numbers for all integer values of x from 0 through 15. Searching for a polynomial formula that produces all primes, however, would be fruitless. Mathematicians proved years ago that no polynomial expression with integer coefficients has only prime values.
But there are other possibilities. So people have continued to look for simple prime-generating functions, and Rutgers graduate student Eric Rowland has just found a new one. In a paper published in the Journal of Integer Sequences, Rowland defines his formula and proves that it generates only 1s and primes.
"Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy," Jeffrey Shallit recently commented on his "Recursivity" blog. A professor at the University of Waterloo, Shallit is editor of the Journal of Integer Sequences.
Here's Rowland's recursive formula for generating primes, as presented by Shallit in his blog.
Define a(1) = 7.
For n greater than or equal to 2, set a(n) = a(n – 1) + gcd(n, a(n – 1)). Here "gcd" means the greatest common divisor.
For example, given that a(1) = 7, a(2) = a(1) + gcd(2, 7) = 7 + 1 = 8.
The prime generator is then a(n) – a(n – 1). The resulting numbers are the so-called first differences of the original sequence.
Here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
Here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
Ignoring the 1s, we find that Rowland's formula generates the primes 5, 3, 11, 3 (again), and 23. If we continue the process and remove duplicates, the formula generates the prime sequence 5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, . . .
Rowland describes his formula in the "A New Kind of Science" blog. He notes that the formula originated in 2003 at the NKS summer school, where participants discover and explore computational systems that exhibit "interesting" behavior.
"This was a surprising discovery, since previously there was no known reliable prime-generating formula that wasn't expressly engineered for this purpose," Rowland said. Rowland went on to prove mathematically that this recurrence produces only 1s and primes. He has created a Mathematica demonstration for exploring the recurrence.
Rowland's formula is unlikely to lead to more efficient ways of generating large primes, a crucial operation in cryptography. His formula produces the prime p only after first generating (p – 3)/2 1s. "So it takes a really long time to generate a large prime," Shallit said. Rowland "has a method for skipping over those useless 1s, but doing so essentially requires an independent test for primality."
Are there other formula's like Rowland's? Recently, French mathematician Benoit Cloitre proved that by setting b(1) = 1 and b(n) = b(n – 1) + lcm(n, b(n – 1)) for n greater than or equal to 2, b(n)/b(n – 1) – 1 is either 1 or prime.
Many other questions remain. Is there anything special about the choice of a(1) = 7? Does Rowland's formula eventually generate all odd primes? Rowland suspects that it does, but there's much more to learn.
August 8, 2008
A Tetrix at Burning Man
Burning Man is an eccentric cultural gathering, a celebration of community and self expression, held annually in the Black Rock Desert of Nevada. Tens of thousands of participants immerse themselves in a week of art, music, theater, technology, and social activism, while camping out on the playa. The event climaxes with the burning of a giant sculpture, the Man.
In recent years, several installations and camps at Burning Man have had a mathematical flavor. The 2003 edition, for example, featured a contorted Möbius-strip jungle gym. Tom Davis, formerly principal scientist at Silicon Graphics, has web pages describing activities at several Burning Man gatherings, including a rudimentary "math camp" in 2007.
This year's Burning Man will be held Aug. 25 to Sept. 1, and mathematician and beadwork artist Gwen L. Fisher of California Polytechnic State University in San Luis Obispo is working with Paul Brown on an adult-sized jungle gym in the form of a Sierpiński tetrahedron (or tetrix) for the event.
The sculpture, called "Bat Country," will stand 21 feet tall and be built from 384 aluminum baseball bats, which form the structure's edges, and 130 12-inch softballs, with one ball at each vertex. It consists, essentially, of 64 tetrahedra. Steel rods, which thread the bats, stabilize the structure.
Based on a fractal structure known as a Sierpiński tetrahedron, "Bat Country" will consist of 64 tetrahedra made from aluminum baseball bats connected by softballs. Courtesy of Gwen Fisher.
"Bat Country" was inspired by Fisher's most popular three-dimensional beaded sculpture, an elegant assemblage of seed beads, bugle beads, and thread. Three views of this beaded fractal framework appeared on the cover of the June 2007 Journal of Mathematics and the Arts, accompanying an article by Fisher and Blake Mellor on the symmetries of beaded beads.
Fisher and her coworkers have now assembled the components into one of the four units that will make up the jungle gym and tested its stability, in preparation for installation at Burning Man 2008.
Fisher stands atop one of four tetrahedral units that will make up the "Bat Country" jungle gym. Courtesy of Gwen Fisher.
Fisher notes that the sculpture looks dramatically different from different points of view. From the outside on the ground, "Bat Country" looks like a triangle with a complex lattice of interior edges, she says. From certain angles, however, the bats align, and the structure appears to be a two-dimensional Sierpiński triangle. Looking upward, a viewer can see intriguing arrays of diamonds or triangles.
Looking upward from inside "Bat Country," reveals a symmetric array of triangles. Courtesy of Gwen Fisher.
After Burning Man, Fisher and Brown hope that their sculptural jungle gym can go on public display in the San Francisco area.
In recent years, several installations and camps at Burning Man have had a mathematical flavor. The 2003 edition, for example, featured a contorted Möbius-strip jungle gym. Tom Davis, formerly principal scientist at Silicon Graphics, has web pages describing activities at several Burning Man gatherings, including a rudimentary "math camp" in 2007.
This year's Burning Man will be held Aug. 25 to Sept. 1, and mathematician and beadwork artist Gwen L. Fisher of California Polytechnic State University in San Luis Obispo is working with Paul Brown on an adult-sized jungle gym in the form of a Sierpiński tetrahedron (or tetrix) for the event.
The sculpture, called "Bat Country," will stand 21 feet tall and be built from 384 aluminum baseball bats, which form the structure's edges, and 130 12-inch softballs, with one ball at each vertex. It consists, essentially, of 64 tetrahedra. Steel rods, which thread the bats, stabilize the structure.
Based on a fractal structure known as a Sierpiński tetrahedron, "Bat Country" will consist of 64 tetrahedra made from aluminum baseball bats connected by softballs. Courtesy of Gwen Fisher.
"Bat Country" was inspired by Fisher's most popular three-dimensional beaded sculpture, an elegant assemblage of seed beads, bugle beads, and thread. Three views of this beaded fractal framework appeared on the cover of the June 2007 Journal of Mathematics and the Arts, accompanying an article by Fisher and Blake Mellor on the symmetries of beaded beads.
Fisher and her coworkers have now assembled the components into one of the four units that will make up the jungle gym and tested its stability, in preparation for installation at Burning Man 2008.
Fisher stands atop one of four tetrahedral units that will make up the "Bat Country" jungle gym. Courtesy of Gwen Fisher.
Fisher notes that the sculpture looks dramatically different from different points of view. From the outside on the ground, "Bat Country" looks like a triangle with a complex lattice of interior edges, she says. From certain angles, however, the bats align, and the structure appears to be a two-dimensional Sierpiński triangle. Looking upward, a viewer can see intriguing arrays of diamonds or triangles.
Looking upward from inside "Bat Country," reveals a symmetric array of triangles. Courtesy of Gwen Fisher.
After Burning Man, Fisher and Brown hope that their sculptural jungle gym can go on public display in the San Francisco area.
Subscribe to:
Posts (Atom)
