Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:****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, February 25, 2010 5:00pm

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

Abstract:

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.