Joshua Trees and Toothpicks


After the Joint Mathematics Meetings in San Diego last month, I took a day off for some botanical and mathematical tourism. I drove up to Joshua Tree National Park, in the high desert beyond the San Bernardino Mountains.

Joshua tree silhouette, Hidden Valley, Joshua Tree National Park

The park’s namesake is the cheerfully odd Yucca brevifolia. According to a park brochure and web site, the Joshua tree used to be a lily, but now it’s an agave. The same brochure explains a little about the growth and development of the plant. Initially, a single stalk grows straight upward and eventually produces a flower at the apex. If that flower is fertilized, the fruiting process destroys the meristem—the actively growing tissue at the tip of the stem. The stalk then bifurcates, producing two limbs of roughly equal size, each with a new apical meristem. The branches grow in unpredictable directions. When the two new growth tips ultimately flower and fruit, they too bifurcate, creating four apices.

Joshua trees with 1 2 4 8 branches

Joshua trees with 20, 21, 22 and 23 terminal tufts of green, bristly leaves.

What could be geekier than that? It’s a symmetrical binary tree, straight out of a computer science textbook. (Except that the textbook would turn the tree upside down.) Abstracting away all the shaggy biological details, a topological model of an idealized Joshua tree would look like this:

Duke window with binary tree pattern 0987

The same motif adorns the windows of a building at Duke University.

Joshua tree 10

In this diagram I have taken the liberty of filling in the unseen, underground portions of the plant by assuming symmetry: I give the root system the same branching structure as the above-ground parts. When this figure is turned 90 degrees, it is known as the H curve; in this orientation I guess it must be the I curve.

Before going any further with this story, I have to admit that the graph-theoretical structure of Yucca brevifolia is not quite as precise and regular as I first thought it might be. Not all the trees are strictly binary. As the sun came up in the park I soon spotted some trifurcations. Later in the day I found even odder branching patterns.

Trifurcated Joshua trees 1315 and 1414

So once again nature tries to implement an algorithm, and before long her mind begins to wander, producing doodles that are nowhere to be found in the specification. But that’s all right. My mind was wandering, too. As I trekked through the groves of Joshua trees, I kept reverting to thoughts of “toothpick trees.” These are structures I had learned about the day before from Neil J. A. Sloane, the sequencemeister of the Online Encyclopedia of Integer Sequences. I had run into Neil on the exhibit floor at the San Diego meeting, where the OEIS Foundation had a booth.

I sensed a connection between Joshua trees and toothpick trees. In the idealized H curve shown above, the branches added in each generation are a little smaller than their parents. The shrinkage factor is \(1/\sqrt{2}\), which I applied to both the length and the thickness of the branches. What happens if the branches don’t shrink? They begin colliding with one another after just three generations. That’s the situation in a toothpick tree. It is formed on essentially the same pattern as the H curve, but without the shrinkage factor; instead we adopt a rule that whenever a branch touches another branch, the colliding tip is “sterilized” and no new branches grow there.

Here is a more precise description from the paper by David Applegate, Omar E. Pol and Sloane that introduced the idea of toothpick trees:

We start with an infinite sheet of graph paper and an infinite supply of line segments of length 1, called “toothpicks.” At stage 1, we place a toothpick on the y-axis and centered at the origin. Each toothpick we place has two ends, and an end is said to be “exposed” if this point on the plane is neither the end nor the midpoint of any other toothpick.

At each subsequent stage, for every exposed toothpick end, we place a toothpick centered at that end and perpendicular to that toothpick. The toothpicks placed at odd-numbered stages are therefore all parallel to the y-axis, while those placed at even-numbered stages are parallel to the x-axis.

I have cobbled together a JavaScript-and-SVG program for assembling and disassembling toothpick trees up to stage n = 128. At this stage the number of toothpicks is 10,923, which is a lot of toothpicks if you buy them in boxes of 250. On the other hand, it’s a whole lot smaller than the 2128–1 branches of the full binary tree.

The interactive version of this illustration relies on “inline SVG,” that is, Scalable Vector Graphics included directly within an HTML document. If you’re seeing a static illustration, without any buttons to click, I’m afraid your browser doesn’t support this feature. In my tests the program works in recent versions of Chrome, Safari, Firefox and Opera; it’s very unlikely to work in RSS readers. There is a stand-alone version of the interactive illustration here. And David Applegate has another “movie version” based on different programming technology.

The successive toothpick totals form sequence A139250 in Sloane’s OEIS. The notes accompanying that listing point out lots of interesting facts about the pattern and the process that generates it. If you run the animation, you can’t help noticing the distinctive behavior as n approaches each integer power of 2, or the repeating pattern in which a square block has a smaller square “ear” at each corner. And no toothpick after the initial one three crosses either the x or the y axis. (When the x or y coordinate is a power of 2, toothpicks from opposite sides meet at points along the axis, but they do not cross it.)

The notes also mention a conjecture, which I assume remains open:

Conjecture: Consider the rectangles in the sieve (including the squares). The area of each rectangle (A=b*c) and the edges (b and c) are powers of 2, but at least one of the edges (b or c) is <= 2.

The rectangles at issue in this conjecture are “open” rectangles, with no toothpicks or parts of toothpicks inside of them. I’ve become curious about more general squares and rectangles, defined as any axis-aligned quadrilateral whose perimeter is traced by an unbroken chain of toothpicks or half-toothpicks, regardless of what’s in the interior. Here are a few squares discovered in a small sample of the toothpick pattern:

Squares in toothpick graph

Matrix of rectangles

The unit of distance in this compilation is half of a toothpick, since that’s the smallest square that can possibly appear. I have highlighted squares with side lengths of 1, 2, 3, 4, 6, 7 and 8 units. Is there a square of side length 5? How about 9 and 17? Looking for rectangles more generally rather than just squares, I enlisted the help of Ros. The black dots in the matrix at right represent all the rectangles we were able to find by hand and eye. (I have not yet written a program to search more systematically.) The red circles at 5-by-5 and 9-by-9 are vacancies that seem particularly intriguing. Do those squares exist anywhere in the toothpick tree? If not, is there some simple argument to explain why?


Into the sun 1337

Just between us pedants, I should mention that neither Joshua trees nor toothpick trees are actually trees. The Joshua tree isn’t woody; the toothpick tree has cycles.

Joshua trees and toothpick trees, natural trees and mathematical trees: They are very different, but I’m fond of them both.

A day spent in the desert sun admiring the idiosyncrasies of Yucca brevifolia feels quite unlike a day spent coding H curves or toothpick trees in JavaScript, or poring over printouts searching for 5-by-5 squares. But I wouldn’t want to have to choose between those activities. And I’m particularly pleased when I can make a connection between them, however tenuous and fanciful.

This entry was posted in biology, mathematics, photography.

8 Responses to Joshua Trees and Toothpicks

  1. Tony Noe says:

    Very nice connection between real and abstract!

  2. Jan Van lent says:

    The OEIS could be helpful to suggest a pattern. The first sequence found in the encyclopedia for 1, 2, 3, 4, 6, 7, 8 which involves powers of two is A023758: \(2^i - 2^j\), \(i >= j\). This suggests the next sizes could be 12, 14, 15, 16, 24.

  3. Gerry Myerson says:

    “And no toothpick except the initial one crosses either the x or the y axis.” The first pair after the initial one cross the y-axis, don’t they?

  4. Rober says:

    2^n-1 –> 1, 3, 5, 9, 15, …
    ¿1 and 3?
    1 = 1 <— no 0s
    2 = 10
    3 = 11 <— no 0s
    4 = 100
    5 = 101 <— 0 inside
    6 = 110
    7 = 111
    8 = 1000
    9 = 1001 <— 0s inside

  5. Leo Broukhis says:

    I invented the D-toothpick pattern in the 1980s (in a biology class after hearing about leaves of ginkgo trees) and I’ve implemented a program generating variations of the pattern as a (winning) entry for the 1995 International Obfuscated C Code Contest: remarks.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

In addition to the basic HTML formatting options offered by the buttons above, you can also enter LaTeX math commands. Enclose LaTeX content in \( ... \) for inline mode or \[ ... \] for display mode.