Toothpick sequence: Difference between revisions
Content deleted Content added
removed Category:Cellular automaton patterns; added Category:Cellular automata using HotCat |
Importing Wikidata short description: "Geometric fractal-like pattern" |
||
| (15 intermediate revisions by 10 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Geometric fractal-like pattern}} |
|||
[[File:Margolus toothpick animated.gif|thumb|The first three steps of the toothpick sequence and its emulation by a [[cellular automaton]] with the [[Margolus neighborhood]]]] |
[[File:Margolus toothpick animated.gif|thumb|The first three steps of the toothpick sequence and its emulation by a [[cellular automaton]] with the [[Margolus neighborhood]]]] |
||
[[File:Toothpick 89.svg|thumb|300px|The 89th stage of the sequence, one of the stages at which ''T''(''n'')/''n''<sup>2</sup> is near its minimum]] |
[[File:Toothpick 89.svg|thumb|300px|The 89th stage of the sequence, one of the stages at which ''T''(''n'')/''n''<sup>2</sup> is near its minimum]] |
||
In [[geometry]], the '''toothpick sequence''' is a sequence of 2-dimensional patterns which can be formed by repeatedly adding line segments ("toothpicks") to the previous pattern in the sequence. |
In [[geometry]], the '''toothpick sequence''' is a sequence of 2-dimensional patterns which can be formed by repeatedly adding line segments ("toothpicks") to the previous pattern in the sequence. |
||
The first stage of the design is a single "toothpick", or line segment. Each stage after the first is formed by taking the previous design and, for every exposed toothpick end, placing another toothpick centered |
The first stage of the design is a single "toothpick", or line segment. Each stage after the first is formed by taking the previous design and, for every exposed toothpick end, placing another toothpick centered at a right angle on that end.<ref name=paper>{{cite conference |
||
| last1 = Applegate | first1 = David | author1-link = David Applegate |
|||
| last2 = Pol | first2 = Omar E. |
|||
| last3 = Sloane | first3 = N. J. A. | author3-link = Neil Sloane |
|||
| arxiv = 1004.3036 |
|||
| contribution = The toothpick sequence and other sequences from cellular automata |
|||
| mr = 2762248 |
|||
| pages = 157–191 |
|||
| series = Congressus Numerantium |
|||
| title = Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing |
|||
| volume = 206 |
|||
| year = 2010| bibcode = 2010arXiv1004.3036A}}</ref> |
|||
This process results in a pattern of growth in which the number of segments at stage ''n'' oscillates with a [[fractal]] pattern between 0.45''n''<sup>2</sup> and 0.67''n''<sup>2</sup>. If ''T''(''n'') denotes the number of segments at stage ''n'', then values of ''n'' for which ''T''(''n'')/''n''<sup>2</sup> is near its maximum occur when ''n'' is near a power of two, while the values for which it is near its minimum occur near numbers that are approximately 1.43 times a power of two.<ref>{{cite journal | |
This process results in a pattern of growth in which the number of segments at stage {{math|''n''}} oscillates with a [[fractal]] pattern between {{math|0.45''n''<sup>2</sup>}} and {{math|0.67''n''<sup>2</sup>}}. If {{math|''T''(''n'')}} denotes the number of segments at stage {{math|''n''}}, then values of {{math|''n''}} for which {{math|''T''(''n'')/''n''<sup>2</sup>}} is near its maximum occur when {{math|''n''}} is near a power of two, while the values for which it is near its minimum occur near numbers that are approximately {{math|1.43}} times a power of two.<ref>{{cite journal |last= Cipra |first= Barry A. |author-link = Barry A. Cipra |year=2010 |title=What Comes Next? |journal=Science |volume=327 |pages=943 |publisher=AAAS | doi=10.1126/science.327.5968.943}}</ref> The structure of stages in the toothpick sequence often resemble the [[T-square (fractal)|T-square]] fractal, or the arrangement of cells in the [[Ulam–Warburton automaton|Ulam–Warburton]] [[cellular automaton]].<ref name=paper /> |
||
All of the bounded regions surrounded by toothpicks in the pattern, but not themselves crossed by toothpicks, must be squares or rectangles.<ref name=paper/> It has been [[conjecture]]d that every open rectangle in the toothpick pattern (that is, a rectangle that is completely surrounded by toothpicks, but has no toothpick crossing its interior) has side lengths and areas that are [[power of two|powers of two]], with one of the side lengths being at most two.<ref>{{ |
All of the bounded regions surrounded by toothpicks in the pattern, but not themselves crossed by toothpicks, must be squares or rectangles.<ref name=paper/> It has been [[conjecture]]d that every open rectangle in the toothpick pattern (that is, a rectangle that is completely surrounded by toothpicks, but has no toothpick crossing its interior) has side lengths and areas that are [[power of two|powers of two]], with one of the side lengths being at most two.<ref>{{Cite OEIS|sequencenumber=A139250|name=Toothpick sequence}}</ref> |
||
==References== |
==References== |
||
| Line 14: | Line 26: | ||
==External links== |
==External links== |
||
*[http://oeis.org/toothlist.html A list of integer sequences related to the Toothpick Sequence] from the [[On-line Encyclopedia of Integer Sequences]]. (note: IDs such as ''A139250'' are IDs within the OEIS, and descriptions of the sequences can be located by entering these IDs in the OEIS [http://oeis.org/ search page].) |
*[http://oeis.org/toothlist.html A list of integer sequences related to the Toothpick Sequence] from the [[On-line Encyclopedia of Integer Sequences]]. (note: IDs such as ''A139250'' are IDs within the OEIS, and descriptions of the sequences can be located by entering these IDs in the OEIS [http://oeis.org/ search page].) |
||
*[http://www2.research.att.com/~david/oeis/toothpick.html A java applet demonstrating the sequence] |
|||
*[http://bit-player.org/2013/joshua-trees-and-toothpicks Joshua Trees and Toothpicks], [[Brian Hayes (scientist)|Brian Hayes]], 8 February 2013 |
*[http://bit-player.org/2013/joshua-trees-and-toothpicks Joshua Trees and Toothpicks], [[Brian Hayes (scientist)|Brian Hayes]], 8 February 2013 |
||
[[Category:Cellular |
[[Category:Cellular automaton patterns]] |
||
[[Category:Combinatorics]] |
[[Category:Combinatorics]] |
||
Latest revision as of 05:45, 13 October 2022
In geometry, the toothpick sequence is a sequence of 2-dimensional patterns which can be formed by repeatedly adding line segments ("toothpicks") to the previous pattern in the sequence.
The first stage of the design is a single "toothpick", or line segment. Each stage after the first is formed by taking the previous design and, for every exposed toothpick end, placing another toothpick centered at a right angle on that end.[1]
This process results in a pattern of growth in which the number of segments at stage n oscillates with a fractal pattern between 0.45n2 and 0.67n2. If T(n) denotes the number of segments at stage n, then values of n for which T(n)/n2 is near its maximum occur when n is near a power of two, while the values for which it is near its minimum occur near numbers that are approximately 1.43 times a power of two.[2] The structure of stages in the toothpick sequence often resemble the T-square fractal, or the arrangement of cells in the Ulam–Warburton cellular automaton.[1]
All of the bounded regions surrounded by toothpicks in the pattern, but not themselves crossed by toothpicks, must be squares or rectangles.[1] It has been conjectured that every open rectangle in the toothpick pattern (that is, a rectangle that is completely surrounded by toothpicks, but has no toothpick crossing its interior) has side lengths and areas that are powers of two, with one of the side lengths being at most two.[3]
References
[edit]- ^ a b c Applegate, David; Pol, Omar E.; Sloane, N. J. A. (2010). "The toothpick sequence and other sequences from cellular automata". Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium. Vol. 206. pp. 157–191. arXiv:1004.3036. Bibcode:2010arXiv1004.3036A. MR 2762248.
- ^ Cipra, Barry A. (2010). "What Comes Next?". Science. 327. AAAS: 943. doi:10.1126/science.327.5968.943.
- ^ Sloane, N. J. A. (ed.). "Sequence A139250 (Toothpick sequence)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
External links
[edit]- A list of integer sequences related to the Toothpick Sequence from the On-line Encyclopedia of Integer Sequences. (note: IDs such as A139250 are IDs within the OEIS, and descriptions of the sequences can be located by entering these IDs in the OEIS search page.)
- Joshua Trees and Toothpicks, Brian Hayes, 8 February 2013