Mathematics – Combinatorics
Scientific paper
2010-04-18
Mathematics
Combinatorics
28 pages, 21 figures. Minor improvements Oct 2, 2010, now 36 pages
Scientific paper
A two-dimensional arrangement of toothpicks is constructed by the following iterative procedure. At stage 1, place a single toothpick of length 1 on a square grid, aligned with the y-axis. At each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end. The resulting structure has a fractal-like appearance. We will analyze the toothpick sequence, which gives the total number of toothpicks after n steps. We also study several related sequences that arise from enumerating active cells in cellular automata. Some unusual recurrences appear: a typical example is that instead of the Fibonacci recurrence, which we may write as a(2+i) = a(i) + a(i+1), we set n = 2^k+i (0 <= i < 2^k), and then a(n)=a(2^k+i)=2a(i)+a(i+1). The corresponding generating functions look like Prod{k >= 0} (1+x^{2^k-1}+2x^{2^k}) and variations thereof.
Applegate David
Pol Omar E.
Sloane N. J. A.
No associations
LandOfFree
The Toothpick Sequence and Other Sequences from Cellular Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Toothpick Sequence and Other Sequences from Cellular Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Toothpick Sequence and Other Sequences from Cellular Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-377613