Last updated: 9/23/04 – New stuff:
#061 computed to 14.7 quintillion
New pics and movie
to prove it
If you’re
wondering what Paterson’s Worms are, you can find a good writeup of the problem
at Sven Kahrkling’s page. I
heard about it when Ed Pegg Jr. mentioned it in the 9/15/03 update to MathPuzzle; later he wrote an article
on it for the MAA, which got discussed
on Slashdot. For a cool applet which lets
you enter rules and see what the resulting worm does, check out Soda’s worm page.
The basic
idea is that a worm travels around a triangular (isometric)
grid, never retracing its path. At each step, the worm looks around at the
5 adjacent points (the one it just came from is not considered) and sees a
particular configuration of taken and open paths. It makes a decision as to
which of the open paths to take, and this becomes a rule: every time from then
on that the worm sees that same configuration of open and taken paths, it must
go the same way as before. All of this is from the worm’s point of view –
directions are not absolute but relative to the worm’s direction of travel,
i.e. your choices are hard left (120 degrees), soft left (60 degrees), straight
ahead, soft right, and hard right. A worm finishes if it reaches a point where
there are no open paths; if you think about it you’ll realize that this can
only happen at the starting point, and that a worm must return there three
times to fill all the paths (it dies on its third return).
As it
turns out there are exactly 412 distinct sets of rules, discarding the obvious
symmetry of whether the first turn is left or right. That’s many fewer than
you’d guess from all the combinations of rules, but many rule sets are
equivalent because their worms don’t use all the rules. According to Sven’s
page, 329 patterns are known to finish, and 71 are clearly infinite (they
obviously walk off into the sunset and will not complete – not a proof, I
know).
That
leaves 11 “undecided” worms – they don’t finish quickly, but have complicated
enough behavior that one can’t immediately dismiss them as clearly infinite.
Thanks to a clever algorithm from Tomas
Rokicki, based on Hashlife,
(his results are here) the
computation has been sped up by many orders of magnitude over a simple
approach. Here’s the status on my computations of them:
|
Pattern number |
Rules |
Lower bound |
Population |
Density (proportion of edges traversed) |
Comments |
|
|
Gardner’s notation |
Sven’s notation |
|||||
|
1a2c3caca4a |
1042015 |
??? |
|
Random
swirls give way to massive triangles after several billion steps. |
||
|
1a2c3aaca4a |
1042020 |
– |
|
Returns
to center at step 57,493,855,199,226, splitting into 062a and 062b |
||
|
062b |
1a2c3aaca4b |
1042022 |
– |
57,493,855,205,905 |
|
Pictures
same as for #062a (difference is all in the last pixel) |
|
1a2d3cbcc4b |
1252121 |
Probably
infinite |
99.99% |
Recursive
hexagons, looks infinite. |
||
|
1a2a3aacc4b |
1420221 |
Probably
infinite |
50.00% |
Hexagon,
grows by contours, looks infinite. |
||
|
1a2a3aaca4b |
1420224 |
– |
72.43% |
|
||
|
1a2a3aacc4a |
1450221 |
Probably
infinite |
50.00% |
Hexagon,
grows by contours, very similar to #183. |
||
|
1a2a3aaca4a |
1450224 |
– |
72.43% |
Same
as #184, rotated 180 degrees. |
||
|
1a2b3cbcc4a |
1525115 |
Probably
infinite |
99.98% |
Recursive
hexagons, very similar to #155. |
||
|
1b2c3bcaa4b |
2014142 |
– |
99.96% |
|
||
|
1b2d3bcaa4b |
2145142 |
– |
99.92% |
|
||
|
1b2a3bcaa4b |
2454142 |
– |
99.96% |
Same
as #378, rotated 120 degrees. |
||
Pictures
for the first two worms were created with the new algorithm, and so some of the
jagged edges are artifacts of its storage scheme – precise image data cannot be
kept at all points. At this point the computation of #061 has tallied about 196
days of CPU time. It may be time to look for a better algorithm.
Links for
each pattern point to directories with pictures (and sometimes movies). In each
filename, the middle number is the number of steps the worm has taken, and the
last number is the log2 of the image’s scale – if the scale is 3,
each pixel is 8 grid points on a side; if the scale is 9, each pixel is 512
points on a side. Images which show completed paths have ‘-done’ in the name. The first color cycle takes 5
million steps, and the cycle length doubles each time after that. The worm’s
starting point is always in the center of the image. Thanks to Fractint for a
nice selection of color palettes.
Movies
Formerly I had a Linux program here which could draw a
movie of a worm’s life, using the same process by which the pictures above were
generated (thanks to the G2 library
for the ability to do easy X graphics). I’ve managed to create real AVIs from
these, which should be much more accessible. You can email me if you miss the
worm_draw program. Making the movies was considerably more difficult than one
would expect; you can read about the tools and
method I used if you like.
Here are
the movies: #061, #062,
#231, #391, #401. You will need the free Xvid codec to view
them; download Windows binaries (click on
“Xvid binaries”) or a Linux
distribution, or build your own from the source at the Xvid home page. I used version 1.0.2 to create
them, so I’d recommend getting at least version 1.0.0.
Higher
resolution and better quality versions of the movies are available if anyone’s
interested, just email me.
Worm Cubes
For the sixth Gathering for Gardner (G4G6) I created about
200 clear acrylic cubes with pictures of the worms layered inside them.
If you’re
interested you can see more pictures and a
description of the process.
You can find me at 
.
Site hits: