Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: The Toothpick Sequence and Other Sequences from Cellular Automata

Speaker: Neil J. A. Sloane, AT&T Shannon Labs

Date: Thursday, April 8, 2010 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The toothpick sequence was invented by Omar Pol (in Buenos Aires). One starts by placing a single toothpick of length 1 on a square grid. At each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end. The result has a remarkable fractal-like structure (which will be illustrated by a movie), and the number of toothpicks added at each stage satisfies an unusual recurrence and generating function. Some related sequences generated by two-dimensional cellular automata will also be discussed. This talk is based on joint work with David Applegate and Omar Pol.