A187212 -id:A187212 - cp's OEIS frontend

A187213 Number of Q-toothpicks added at n-th stage to the structure of A187212.

0, 1, 2, 2, 4, 4, 8, 10, 8, 4, 8, 12, 12, 16, 28, 30, 16, 4, 8, 12, 12, 16, 28, 32, 20, 16, 28, 36, 40, 60, 88, 78, 32, 4, 8, 12, 12, 16, 28, 32, 20, 16, 28, 36, 40, 60, 88, 80, 36, 16, 28, 36, 40, 60, 88, 84, 56, 60, 92, 112

Offset: 0

Omar E. Pol, Mar 22 2011

nonn

Essentially the first differences of A187212.

			Contribution from Omar E. Pol, Mar 29 2011 (Start):
If written as a triangle begins:
0,
1,
2,
2,4,
4,8,10,8,
4,8,12,12,16,28,30,16,
4,8,12,12,16,28,32,20,16,28,36,40,60,88,78,32,
(End)

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Nathaniel Johnston, The Q-Toothpick Cellular Automaton
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A139250, A139251, A187211, A187212, A187221.

It appears that if n = 2^k - 1, for k >= 2, then a(n) = A139251(n) - 2 otherwise a(n) = A139251(n). - Omar E. Pol, Mar 30 2011

Terms after a(24) from Nathaniel Johnston, Mar 28 2011

A187214 Number of gulls (or G-toothpicks) added at n-th stage in the first quadrant of the gullwing structure of A187212.

Original entry on oeis.org

0, 1, 1, 2, 2, 4, 5, 4, 2, 4, 6, 6, 8, 14, 15, 8, 2, 4, 6, 6, 8, 14, 16, 10, 8, 14, 18, 20, 30, 44, 39, 16, 2, 4, 6, 6, 8, 14, 16, 10, 8, 14, 18, 20, 30, 44, 40, 18, 8, 14, 18, 20, 30, 44, 42, 28, 30, 46, 56, 70, 104, 128, 95

Offset: 1

Omar E. Pol, Mar 22 2011, Apr 06 2011

nonn

It appears that both a(2) and a(2^k - 1) are odd numbers, for k >= 2. Other terms are even numbers.

			At stage 1 we start in the first quadrant from a Q-toothpick centered at (1,0) with its endpoints at (0,0) and (1,1). There are no gulls in the structure, so a(1) = 0.
At stage 2 we place a gull (or G-toothpick) with its midpoint at (1,1) and its endpoints at (2,0) and (2,2), so a(2) = 1. There is only one exposed midpoint at (2,2).
At stage 3 we place a gull with its midpoint at (2,2), so a(3) = 1. There are two exposed endpoints.
At stage 4 we place two gulls, so a(4) = 2. There are two exposed endpoints.
At stage 5 we place two gulls, so a(5) = 2. There are four exposed endpoints.
And so on.
If written as a triangle begins:
0,
1,
1,2,
2,4,5,4,
2,4,6,6,8,14,15,8,
2,4,6,6,8,14,16,10,8,14,18,20,30,44,39,16,
2,4,6,6,8,14,16,10,8,14,18,20,30,44,40,18,8,14,18,20,30,44,42,28,...
It appears that rows converge to A151688.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A099035, A151550, A151688, A187210, A187211, A187212, A187213, A187220.

read("transforms3") ;
L := BFILETOLIST("b187212.txt") ;
A187213 := DIFF(L) ;
seq( op(n,A187213)/2,n=2..nops(A187213)) ; # R. J. Mathar, Mar 30 2011

a(1)=0. a(n) = A187213(n)/2, for n >= 2.

It appears that a(2^k - 1) = A099035(k-1), for k >= 2.

A139250 Toothpick sequence (see Comments lines for definition).

Original entry on oeis.org

0, 1, 3, 7, 11, 15, 23, 35, 43, 47, 55, 67, 79, 95, 123, 155, 171, 175, 183, 195, 207, 223, 251, 283, 303, 319, 347, 383, 423, 483, 571, 651, 683, 687, 695, 707, 719, 735, 763, 795, 815, 831, 859, 895, 935, 995, 1083, 1163, 1199, 1215, 1243, 1279, 1319, 1379

Offset: 0

Omar E. Pol, Apr 24 2008

A toothpick is a copy of the closed interval [-1,1]. (In the paper, we take it to be a copy of the unit interval [-1/2, 1/2].)
We start at stage 0 with no toothpicks.
At stage 1 we place a toothpick in the vertical direction, anywhere in the plane.
In general, given a configuration of toothpicks in the plane, at the next stage we add as many toothpicks as possible, subject to certain conditions:
- Each new toothpick must lie in the horizontal or vertical directions.
- Two toothpicks may never cross.
- Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.
The sequence gives the number of toothpicks after n stages. A139251 (the first differences) gives the number added at the n-th stage.
Call the endpoint of a toothpick "exposed" if it does not touch any other toothpick. The growth rule may be expressed as follows: at each stage, new toothpicks are placed so their midpoints touch every exposed endpoint.
This is equivalent to a two-dimensional cellular automaton. The animations show the fractal-like behavior.
After 2^k - 1 steps, there are 2^k exposed endpoints, all located on two lines perpendicular to the initial toothpick. At the next step, 2^k toothpicks are placed on these lines, leaving only 4 exposed endpoints, located at the corners of a square with side length 2^(k-1) times the length of a toothpick. - M. F. Hasler, Apr 14 2009 and others. For proof, see the Applegate-Pol-Sloane paper.
If the third condition in the definition is changed to "- Each new toothpick must have at exactly one of its endpoints touching the midpoint of an existing toothpick" then the same sequence is obtained. The configurations of toothpicks are of course different from those in the present sequence. But if we start with the configurations of the present sequence, rotate each toothpick a quarter-turn, and then rotate the whole configuration a quarter-turn, we obtain the other configuration.
If the third condition in the definition is changed to "- Each new toothpick must have at least one of its endpoints touching the midpoint of an existing toothpick" then the sequence n^2 - n + 1 is obtained, because there are no holes left in the grid.
A "toothpick" of length 2 can be regarded as a polyedge with 2 components, both on the same line. At stage n, the toothpick structure is a polyedge with 2*a(n) components.
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.
In the toothpick structure, if n >> 1, we can see some patterns that look like "canals" and "diffraction patterns". For example, see the Applegate link "A139250: the movie version", then enter n=1008 and click "Update". See also "T-square (fractal)" in the Links section. - Omar E. Pol, May 19 2009, Oct 01 2011
From Benoit Jubin, May 20 2009: The web page "Gallery" of Chris Moore (see link) has some nice pictures that are somewhat similar to the pictures of the present sequence. What sequences do they correspond to?
For a connection to Sierpiński triangle and Gould's sequence A001316, see the leftist toothpick triangle A151566.
Eric Rowland comments on Mar 15 2010 that this toothpick structure can be represented as a 5-state CA on the square grid. On Mar 18 2010, David Applegate showed that three states are enough. See links.
Equals row sums of triangle A160570 starting with offset 1; equivalent to convolving A160552: (1, 1, 3, 1, 3, 5, 7, ...) with (1, 2, 2, 2, ...). Equals A160762: (1, 0, 2, -2, 2, 2, 2, -6, ...) convolved with 2*n - 1: (1, 3, 5, 7, ...). Starting with offset 1 equals A151548: [1, 3, 5, 7, 5, 11, 17, 15, ...] convolved with A078008 signed (A151575): [1, 0, 2, -2, 6, -10, 22, -42, 86, -170, 342, ...]. - Gary W. Adamson, May 19 2009, May 25 2009
For a three-dimensional version of the toothpick structure, see A160160. - Omar E. Pol, Dec 06 2009
From Omar E. Pol, May 20 2010: (Start)
Observation about the arrangement of rectangles:
It appears there is a nice pattern formed by distinct modular substructures: a central cross surrounded by asymmetrical crosses (or "hidden crosses") of distinct sizes and also by "nuclei" of crosses.
Conjectures: after 2^k stages, for k >= 2, and for m = 1 to k - 1, there are 4^(m-1) substructures of size s = k - m, where every substructure has 4*s rectangles. The total number of substructures is equal to (4^(k-1)-1)/3 = A002450(k-1). For example: If k = 5 (after 32 stages) we can see that:
a) There is a central cross, of size 4, with 16 rectangles.
b) There are four hidden crosses, of size 3, where every cross has 12 rectangles.
c) There are 16 hidden crosses, of size 2, where every cross has 8 rectangles.
d) There are 64 nuclei of crosses, of size 1, where every nucleus has 4 rectangles.
Hence the total number of substructures after 32 stages is equal to 85. Note that in every arm of every substructure, in the potential growth direction, the length of the rectangles are the powers of 2. (See illustrations in the links. See also A160124.) (End)
It appears that the number of grid points that are covered after n-th stage of the toothpick structure, assuming the toothpicks have length 2*k, is equal to (2*k-2)*a(n) + A147614(n), k > 0. See the formulas of A160420 and A160422. - Omar E. Pol, Nov 13 2010
Version "Gullwing": on the semi-infinite square grid, at stage 1, we place a horizontal "gull" with its vertices at [(-1, 2), (0, 1), (1, 2)]. At stage 2, we place two vertical gulls. At stage 3, we place four horizontal gulls. a(n) is also the number of gulls after n-th stage. For more information about the growth of gulls see A187220. - Omar E. Pol, Mar 10 2011
From Omar E. Pol, Mar 12 2011: (Start)
Version "I-toothpick": we define an "I-toothpick" to consist of two connected toothpicks, as a bar of length 2. An I-toothpick with length 2 is formed by two toothpicks with length 1. The midpoint of an I-toothpick is touched by its two toothpicks. a(n) is also the number of I-toothpicks after n-th stage in the I-toothpick structure. The I-toothpick structure is essentially the original toothpick structure in which every toothpick is replaced by an I-toothpick. Note that in the physical model of the original toothpick structure the midpoint of a wooden toothpick of the new generation is superimposed on the endpoint of a wooden toothpick of the old generation. However, in the physical model of the I-toothpick structure the wooden toothpicks are not overlapping because all wooden toothpicks are connected by their endpoints. For the number of toothpicks in the I-toothpick structure see A160164 which also gives the number of gullwing in a gullwing structure because the gullwing structure of A160164 is equivalent to the I-toothpick structure. It also appears that the gullwing sequence A187220 is a supersequence of the original toothpick sequence A139250 (this sequence).
For the connection with the Ulam-Warburton cellular automaton see the Applegate-Pol-Sloane paper and see also A160164 and A187220.
(End)
A version in which the toothpicks are connected by their endpoints: on the semi-infinite square grid, at stage 1, we place a vertical toothpick of length 1 from (0, 0). At stage 2, we place two horizontal toothpicks from (0,1), and so on. The arrangement looks like half of the I-toothpick structure. a(n) is also the number of toothpicks after the n-th. - Omar E. Pol, Mar 13 2011
Version "Quarter-circle" (or Q-toothpick): a(n) is also the number of Q-toothpicks after the n-th stage in a Q-toothpick structure in the first quadrant. We start from (0,1) with the first Q-toothpick centered at (1, 1). The structure is asymmetric. For a similar structure but starting from (0, 0) see A187212. See A187210 and A187220 for more information. - Omar E. Pol, Mar 22 2011
Version "Tree": It appears that a(n) is also the number of toothpicks after the n-th stage in a toothpick structure constructed following a special rule: the toothpicks of the new generation have length 4 when they are placed on the infinite square grid (note that every toothpick has four components of length 1), but after every stage, one (or two) of the four components of every toothpick of the new generation is removed, if such component contains an endpoint of the toothpick and if such endpoint is touching the midpoint or the endpoint of another toothpick. The truncated endpoints of the toothpicks remain exposed forever. Note that there are three sizes of toothpicks in the structure: toothpicks of lengths 4, 3 and 2. A159795 gives the total number of components in the structure after the n-th stage. A153006 (the corner sequence of the original version) gives 1/4 of the total of components in the structure after the n-th stage. - Omar E. Pol, Oct 24 2011
From Omar E. Pol, Sep 16 2012: (Start)
It appears that a(n)/A147614(n) converges to 3/4.
It appears that a(n)/A160124(n) converges to 3/2.
It appears that a(n)/A139252(n) converges to 3.
Also:
It appears that A147614(n)/A160124(n) converges to 2.
It appears that A160124(n)/A139252(n) converges to 2.
It appears that A147614(n)/A139252(n) converges to 4.
(End)
It appears that a(n) is also the total number of ON cells after n-th stage in a quadrant of the structure of the cellular automaton described in A169707 plus the total number of ON cells after n+1 stages in a quadrant of the mentioned structure, without its central cell. See the illustration of the NW-NE-SE-SW version in A169707. See also the connection between A160164 and A169707. - Omar E. Pol, Jul 26 2015
On the infinite Cairo pentagonal tiling consider the symmetric figure formed by two non-adjacent pentagons connected by a line segment joining two trivalent nodes. At stage 1 we start with one of these figures turned ON. The rule for the next stages is that the concave part of the figures of the new generation must be adjacent to the complementary convex part of the figures of the old generation. a(n) gives the number of figures that are ON in the structure after n-th stage. A160164(n) gives the number of ON cells in the structure after n-th stage. - Omar E. Pol, Mar 29 2018
From Omar E. Pol, Mar 06 2019: (Start)
The "word" of this sequence is "ab". For further information about the word of cellular automata see A296612.
Version "triangular grid": a(n) is also the total number of toothpicks of length 2 after n-th stage in the toothpick structure on the infinite triangular grid, if we use only two of the three axes. Otherwise, if we use the three axes, so we have the sequence A296510 which has word "abc".
The normal toothpick structure can be considered a superstructure of the Ulam-Warburton celular automaton since A147562(n) equals here the total number of "hidden crosses" after 4*n stages, including the central cross (beginning to count the crosses when their "nuclei" are totally formed with 4 quadrilaterals). Note that every quadrilateral in the structure belongs to a "hidden cross".
Also, the number of "hidden crosses" after n stages equals the total number of "flowers with six petals" after n-th stage in the structure of A323650, which appears to be a "missing link" between this sequence and A147562.
Note that the location of the "nuclei of the hidden crosses" is very similar (essentially the same) to the location of the "flowers with six petals" in the structure of A323650 and to the location of the "ON" cells in the version "one-step bishop" of the Ulam-Warburton cellular automaton of A147562. (End)
From Omar E. Pol, Nov 27 2020: (Start)
The simplest substructures are the arms of the hidden crosses. Each closed region (square or rectangle) of the structure belongs to one of these arms. The narrow arms have regions of area 1, 2, 4, 8, ... The broad arms have regions of area 2, 4, 8, 16 , ... Note that after 2^k stages, with k >= 3, the narrow arms of the main hidden crosses in each quadrant frame the size of the toothpick structure after 2^(k-1) stages.
Another kind of substructure could be called "bar chart" or "bar graph". This substructure is formed by the rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure after 2^k stages, with k >= 2. The height of these successive regions gives the first 2^(k-1) - 1 terms from A006519. For example: if k = 5 the respective heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1]. The area of these successive regions gives the first 2^(k-1) - 1 terms of A171977. For example: if k = 5 the respective areas are [2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2].
For a connection to Mersenne primes (A000668) and perfect numbers (A000396) see A153006.
For a representation of the Wagstaff primes (A000979) using the toothpick structure see A194810.
For a connection to stained glass windows and a hidden curve see A336532. (End)
It appears that the graph of a(n) bears a striking resemblance to the cumulative distribution function F(x) for X the random variable taking values in [0,1], where the binary expansion of X is given by a sequence of independent coin tosses with probability 3/4 of being 1 at each bit. It appears that F(n/2^k)*(2^(2k+1)+1)/3 approaches a(n) for k large. - James Coe, Jan 10 2022

			a(10^10) = 52010594272060810683. - _David A. Corneth_, Mar 26 2015

D. Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191
L. D. Pryor, The Inheritance of Inflorescence Characters in Eucalyptus, Proceedings of the Linnean Society of New South Wales, V. 79, (1954), p. 81, 83.
Richard P. Stanley, Enumerative Combinatorics, volume 1, second edition, chapter 1, exercise 95, figure 1.28, Cambridge University Press (2012), p. 120, 166.

N. J. A. Sloane, Table of n, a(n) for n = 0..65535
AlgoMotion, Toothpick Sequence Visualized with Circle of Fifths Harmony | 256 Steps, Youtube video (2024).
David Applegate, The movie version
David Applegate, Animation of first 32 stages
David Applegate, Animation of first 64 stages
David Applegate, Animation of first 128 stages
David Applegate, Animation of first 256 stages
David Applegate, C++ program to generate these animations - creates postscript for a specific n
David Applegate, Generates many postscripts, converts them to gifs, and glues the gifs together into an animation
David Applegate, Generates b-files for A139250, A139251, A147614
David Applegate, The b-files for A139250, A139251, A147614 side-by-side
David Applegate, A three-state CA for the toothpick structure
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at arXiv:1004.3036v2
Joe Champion, Ultimate toothpick pattern, Photo 1, Photo 2, Photo 3, Photo 4, Boise Math Circles, Boise State University. [Links updated by _P. Michael Hutchins_, Mar 03 2018]
Barry Cipra, What comes next?, Science (AAAS) 327: 943.
Steven R. Finch, Toothpicks and Live Cells, July 21, 2015. [Cached copy, with permission of the author]
Ulrich Gehmann, Martin Reiche, World mountain machine, Berlin, (2014), first edition, p. 205, 238, 253.
Mats Granvik, Additional illustration: Number blocks where each number tells how many times a point on the square grid is crossed or connected to by a toothpick, Jun 21 2009.
Gordon Hamilton, Three integer sequences from recreational mathematics, Video (2013?).
J. K. Hamilton, I. R. Hooper, and C. R. Lawrence, Exploring microwave absorption by non-periodic metasurfaces, Advanced Electromagnetics, 10(3), 1-6 (2021).
M. F. Hasler, Illustration of initial terms
M. F. Hasler, Illustrations (Three slides)
Brian Hayes, Joshua Trees and Toothpicks
Brian Hayes, Idealized Joshua tree, a figure from "Joshua Trees and Toothpicks" (see preceding link)
Brian Hayes, The Toothpick Sequence - Bit-Player
Benoit Jubin, Illustration of initial terms
Mathemaesthetics, 2'796'203 Toothpicks, 2'048 Generations, Youtube video (2021).
Ayliean McDonald, Toothpick fractal and breaking rules, Youtube video (2021)
Chris Moore, Gallery, see the section on David Griffeath's Cellular Automata.
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of initial terms using "gulls" (or G-toothpicks)
Omar E. Pol, Illustration of initial terms using quarter-circles (or Q-toothpicks)
Omar E. Pol, Illustration of the toothpick structure (after 23 steps)
Omar E. Pol, Illustration of patterns in the toothpick structure (after 32 steps)
Omar E. Pol, Illustration of patterns in the toothpick structure (after 32 steps) [Cached copy, with permission]
Omar E. Pol, Illustration of initial terms of A139250, A160120, A147562 (Overlapping figures)
Omar E. Pol, Illustration of initial terms of A160120, A161206, A161328, A161330 (triangular grid and toothpick structure)
Omar E. Pol, Illustration of the substructures in the first quadrant (As pieces of a puzzle), after 32 stages
Omar E. Pol, Illustration of the potential growth direction of the arms of the substructures, after 32 stages
Olbaid Fractalium, Toothpick sequence Part 1, (Watch from minute 0:00 until 3:13), Youtube video (2023).
Programing Puzzles & Code Golf Stack Exchange, Generate toothpick sequence
L. D. Pryor, Illustration of initial terms (Fig. 2a)
L. D. Pryor, The Inheritance of Inflorescence Characters in Eucalyptus, Proceedings of the Linnean Society of New South Wales, V. 79, (1954), p. 79-89.
E. Rowland, Toothpick sequence from cellular automaton on square grid
E. Rowland, Initial stages of toothpick sequence from cellular automaton on square grid (includes Mathematica code)
K. Ryde, ToothpickTree.
Daniel Shiffman, Coding Challenge #126: Toothpicks, The Coding Train video (2018)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane and Brady Haran, Terrific Toothpick Patterns, Numberphile video (2018)
Alex van den Brandhof and Paul Levrie, Tandenstokerrij, Pythagoras, Wiskundetijdschrift voor Jongeren, 55ste Jaargang, Nummer 6, Juni 2016, (see the cover, pages 1, 18, 19 and the back cover).
Lu Wang, Minecraft Toothpicks N = 53
Wikipedia, Cairo pentagonal tiling
Wikipedia, H tree
Wikipedia, Toothpick sequence
Wikipedia, T-square (fractal)
Index entries for sequences related to toothpick sequences
Index entries for sequences related to cellular automata

Cf. A000079, A002450, A006519, A139251, A139252, A139253, A147614, A139560, A152968, A152978, A152980, A152998, A153000, A153001, A153003, A153004, A153006, A153007, A000217, A007583, A007683, A000396, A000225, A000668, A006516, A006095, A019988, A160570, A160552, A000969, A001316, A151566, A160406, A160408, A160702, A078008, A151548, A001045, A147562, A160124, A160120, A160160, A160170, A160172, A161206, A161328, A161330, A171977, A194810, A296510, A296612, A299476, A299478, A323650, A336532.

G := (x/((1-x)*(1+2*x))) * (1 + 2*x*mul(1+x^(2^k-1)+2*x^(2^k),k=0..20)); # N. J. A. Sloane, May 20 2009, Jun 05 2009
# From N. J. A. Sloane, Dec 25 2009: A139250 is T, A139251 is a.
a:=[0,1,2,4]; T:=[0,1,3,7]; M:=10;
for k from 1 to M do
a:=[op(a),2^(k+1)];
T:=[op(T),T[nops(T)]+a[nops(a)]];
for j from 1 to 2^(k+1)-1 do
a:=[op(a), 2*a[j+1]+a[j+2]];
T:=[op(T),T[nops(T)]+a[nops(a)]];
od: od: a; T;

CoefficientList[ Series[ (x/((1 - x)*(1 + 2x))) (1 + 2x*Product[1 + x^(2^k - 1) + 2*x^(2^k), {k, 0, 20}]), {x, 0, 53}], x] (* Robert G. Wilson v, Dec 06 2010 *)
a[0] = 0; a[n_] := a[n] = Module[{m, k}, m = 2^(Length[IntegerDigits[n, 2]] - 1); k = (2m^2+1)/3; If[n == m, k, k + 2 a[n - m] + a[n - m + 1] - 1]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 06 2018, after David A. Corneth *)

A139250(n,print_all=0)={my(p=[], /* set of "used" points. Points are written as complex numbers, c=x+iy. Toothpicks are of length 2 */
ee=[[0,1]], /* list of (exposed) endpoints. Exposed endpoints are listed as [c,d] where c=x+iy is the position of the endpoint, and d (unimodular) is the direction */
c,d,ne, cnt=1); print_all && print1("0,1"); n<2 && return(n);
for(i=2,n, p=setunion(p, Set(Mat(ee~)[,1])); /* add endpoints (discard directions) from last move to "used" points */
ne=[]; /* new (exposed) endpoints */
for( k=1, #ee, /* add endpoints of new toothpicks if not among the used points */
setsearch(p, c=ee[k][1]+d=ee[k][2]*I) || ne=setunion(ne,Set([[c,d]]));
setsearch(p, c-2*d) || ne=setunion(ne,Set([[c-2*d,-d]]));
); /* using Set() we have the points sorted, so it's easy to remove those which finally are not exposed because they touch a new toothpick */
forstep( k=#ee=eval(ne), 2, -1, ee[k][1]==ee[k-1][1] && k-- && ee=vecextract(ee,Str("^"k"..",k+1)));
cnt+=#ee; /* each exposed endpoint will give a new toothpick */
print_all && print1(","cnt));cnt} \\ M. F. Hasler, Apr 14 2009

\\works for n > 0
a(n) = {my(k = (2*msb(n)^2 + 1) / 3); if(n==msb(n),k , k + 2*a(n-msb(n)) + a(n - msb(n) + 1) - 1)}
msb(n)=my(t=0);while(n>>t>0,t++);2^(t-1)\\ David A. Corneth, Mar 26 2015

def msb(n):
    t = 0
    while n>>t > 0:
        t += 1
    return 2**(t - 1)
def a(n):
    k = (2 * msb(n)**2 + 1) / 3
    return 0 if n == 0 else k if n == msb(n) else k + 2*a(n - msb(n)) + a(n - msb(n) + 1) - 1
[a(n) for n in range(101)]  # Indranil Ghosh, Jul 01 2017, after David A. Corneth's PARI script

a(2^k) = A007583(k), if k >= 0.
a(2^k-1) = A006095(k+1), if k >= 1.
a(A000225(k)) - a((A000225(k)-1)/2) = A006516(k), if k >= 1.
a(A000668(k)) - a((A000668(k)-1)/2) = A000396(k), if k >= 1.
G.f.: (x/((1-x)*(1+2*x))) * (1 + 2*x*Product_{k>=0} (1 + x^(2^k-1) + 2*x^(2^k))). - N. J. A. Sloane, May 20 2009, Jun 05 2009
One can show that lim sup a(n)/n^2 = 2/3, and it appears that lim inf a(n)/n^2 is 0.451... - Benoit Jubin, Apr 15 2009 and Jan 29 2010, N. J. A. Sloane, Jan 29 2010
Observation: a(n) == 3 (mod 4) for n >= 2. - Jaume Oliver Lafont, Feb 05 2009
a(2^k-1) = A000969(2^k-2), if k >= 1. - Omar E. Pol, Feb 13 2010
It appears that a(n) = (A187220(n+1) - 1)/2. - Omar E. Pol, Mar 08 2011
a(n) = 4*A153000(n-2) + 3, if n >= 2. - Omar E. Pol, Oct 01 2011
It appears that a(n) = A160552(n) + (A169707(n) - 1)/2, n >= 1. - Omar E. Pol, Feb 15 2015
It appears that a(n) = A255747(n) + A255747(n-1), n >= 1. - Omar E. Pol, Mar 16 2015
Let n = msb(n) + j where msb(n) = A053644(n) and let a(0) = 0. Then a(n) = (2 * msb(n)^2 + 1)/3 + 2 * a(j) + a(j+1) - 1. - David A. Corneth, Mar 26 2015
It appears that a(n) = (A169707(n) - 1)/4 + (A169707(n+1) - 1)/4, n >= 1. - Omar E. Pol, Jul 24 2015

Verified and extended, a(49)-a(53), using the given PARI code by M. F. Hasler, Apr 14 2009
Edited by N. J. A. Sloane, Apr 29 2009, incorporating comments from Omar E. Pol, M. F. Hasler, Rob Pratt, Jaume Oliver Lafont, Franklin T. Adams-Watters, R. J. Mathar, David W. Wilson, David Applegate, Benoit Jubin and others.
Further edited by N. J. A. Sloane, Jan 28 2010

A187210 Q-toothpick sequence (see Comments for precise definition).

Original entry on oeis.org

0, 1, 5, 12, 24, 46, 66, 88, 128, 182, 222, 244, 284, 338, 394, 464, 584, 718, 790, 812, 852, 906, 962, 1032, 1152, 1286, 1374, 1444, 1564, 1714, 1882, 2128, 2488, 2814, 2950, 2972, 3012, 3066, 3122, 3192, 3312, 3446, 3534, 3604, 3724, 3874, 4042, 4288, 4648, 4974, 5126, 5196, 5316, 5466, 5634, 5880, 6240, 6582, 6814, 7060, 7436, 7890, 8458, 9296, 10328

Offset: 0

Omar E. Pol, Mar 07 2011

nonn

We define a "Q-toothpick" to be a quarter-circle. The length of a Q-toothpick is equal to Pi/2 = 1.570796...
In order to construct this sequence we use the following rules:
- Each new Q-toothpick must lie on the square grid (or circular grid) such that the Q-toothpick endpoints coincide with two opposite vertices of a unit square.
- Each exposed endpoint of the Q-toothpicks of the old generation must be touched by the endpoints of two q-toothpicks of new generation without creating a corner or vertex between these three arcs such that the couple of new Q-toothpicks should look like a "gullwing".
Note that in the Q-toothpick structure sometimes there is also an internal growth of the Q-toothpicks.
The sequence gives the number of Q-toothpicks in the structure after n stages. A187211 (the first differences) gives the number of Q-toothpicks added at n-th stage.
Note that the structure of the Q-toothpick cellular automaton contains distinct types of geometrical figures, for example: circles, diamonds, hearts, heads or flower vases (which appears only on the main diagonal) and also an infinity family of objects (blobs) where every object is a closed region which contains 2^k virtual circles with radius 1 and 2^k-1 virtual diamonds, for example: a 2 X 2 object is a closed region which contains exactly four virtual circles and three virtual diamonds, a 2 X 4 object is a closed region which contains exactly 8 virtual circles and 7 virtual diamonds, etc. Note that a "heart" can be considered a 1 X 2 object which contains two virtual circles and a virtual diamond. What is the better name for these figures? Note that there is a correspondence between this last family of objects and the squares and rectangles of the hidden crosses in the toothpick structure of A139250. For more information about the connection with the toothpick sequence see A139250, A160164 and A187220.
It appears that the number of hearts present in the n-th generation equals the number of rectangles of area = 2 present in the (n-2)nd generation of the toothpick structure of A139250, assuming the toothpicks have length 2, if n >= 3 (see also A188346 and A211008). - Omar E. Pol, Sep 30 2012
From Omar E. Pol, Jan 23 2016: (Start)
Consider the initial Q-toothpick with the virtual center at (0,0) and its endpoints at (0,1) and (1,0).
If n is a power of 2 plus 2 and n >> 1 then the structure of this C.A. essentially looks like a square which contains four parts (or sectors) as follows:
1) NW quadrant, but whose origin is at (-1,1). In this quadrant the number of Q-toothpicks after n generations equals the number of toothpicks in the toothpick structure of A139250 after n-2 generations, if n >= 2. Note that here the toothpick sequence A139250 is represented with Q-toothpicks arranged in an asymmetric structure.
2) SE quadrant, but whose origin is at (1,-1). This quadrant is a reflected copy of the NW quadrant, hence the number of Q-toothpicks after n generations equals A139250(n-2), n >= 2, the same as in the NW quadrant.
3) SW quadrant, but with the origin in the first quadrant at (1,1). In this quadrant the number of Q-toothpicks after n generations is 1 + A267694(n-1), n >= 1.
4) NE quasi-quadrant. In this sector the number of Q-toothpicks after n-generations is A267698(n-2) - 2, if n >= 6. (End)
After the first few generations the behavior is similar to the Gullwing cellular automaton of A187220, but the growth is faster than A187220 and thus it's much faster than A139250. For an animation see Applegate's The movie version in the Links section. - Omar E. Pol, Sep 13 2016

			From _Omar E. Pol_, Apr 02 2016: (Start)
Examples that are related to the toothpick sequence A139250 (see the first formula):
For n = 5 we have that A139250(5-2) = 7, A267698(5-2) = 13, A267694(5-1) = 16 and m = 3, so a(5) = 2*7 + 13 + 16 + 3 = 46.
For n = 6 we have that A139250(6-2) = 11, A267698(6-2) = 25, A267694(6-1) = 20 and m = -1, so a(6) = 2*11 + 25 + 20 - 1 = 66. (End)
From _Omar E. Pol_, Sep 13 2016: (Start)
Examples that are related to the Gullwing sequence A187220 (see the second formula):
For n = 5 we have that A187220(5-1) = 15, A267698(5-2) = 13, A267694(5-1) = 16 and m = 2, so a(5) = 15 + 13 + 16 + 2 = 46.
For n = 6 we have that A187220(6-1) = 23, A267698(6-2) = 25, A267694(6-1) = 20 and m = -2, so a(6) = 23 + 25 + 20 - 2 = 66. (End)

A. Adamatzky and G. J. Martinez, Designing Beauty: The Art of Cellular Automata, Springer, 2016, pages 59, 62 (note that the Q-toothpick cellular automaton is erroneously attributed to Nathaniel Johnston).

Nathaniel Johnston, Table of n, a(n) for n = 0..177
David Applegate, The movie version
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Elisabet Edvardsson and Eva Mossberg, The Q-toothpick Cellular Automaton, Journal of Cellular Automata, Vol. 14, Issue 1-2, (2019), p. 51-68.
Nathaniel Johnston, Animation of first 19 generations
Nathaniel Johnston, Illustration of a(5) = 46, "Front Matter" 2015. The College Mathematics Journal 46 (1). Mathematical Association of America: 1-1. doi:10.4169/college.math.j.46.1.fm.
Nathaniel Johnston, The Q-Toothpick Cellular Automaton
Nathaniel Johnston, The Q-Toothpick post in ConwayLife.com
Omar E. Pol, Illustration of initial terms
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata
Index entries for sequences related to toothpick sequences

Cf. A139250, A160164, A187211, A187212, A187220, A188344, A188345, A188346, A267694, A267698.

a(0)=0; a(1)=1; a(n) = 2*A139250(n-2) + A267698(n-2) + A267694(n-1) + m, where m = 3 if 2 <= n <= 5 and m = -1 if n>=6 (note that 2*A139250(n-2) can be replaced with A160164(n-2)). - Omar E. Pol, Jan 23 2016

a(n) = A187220(n-1) + A267698(n-2) + A267694(n-1) + m, where m = 2 if 2 <= n <= 5 and m = -2 if n >= 6. - Omar E. Pol, Sep 13 2016

Terms a(8) and beyond from Nathaniel Johnston, Mar 26 2011
Comments edited by Omar E. Pol, Mar 28 2011
Second rule clarified by Omar E. Pol, Apr 06 2011

A182838 H-toothpick sequence in the first quadrant starting with a D-toothpick placed on the diagonal [(0,1), (1,2)] (see Comments for precise definition).

Original entry on oeis.org

0, 1, 3, 7, 11, 15, 21, 31, 39, 43, 49, 61, 77, 91, 105, 127, 143, 147, 153, 165, 181, 197, 217, 249, 285, 307, 321, 349, 391, 431, 467, 517, 549, 553, 559, 571, 587, 603, 623, 655, 691, 715

Offset: 0

Omar E. Pol, Dec 12 2010

An H-toothpick sequence is a toothpick sequence on a square grid that resembles a partial honeycomb of hexagons.
The structure has two types of elements: the classic toothpicks with length 1 and the "D-toothpicks"  with length sqrt(2).
Classic toothpicks are placed in the vertical direction and D-toothpicks are placed in a diagonal direction.
Each hexagon has area = 4.
The network looks like an elongated hexagonal lattice placed on the square grid so that all nodes of the hexagonal net coincide with some of the grid points of the square grid. Each node in the hexagonal network is represented with coordinates x,y.
The sequence gives the number of toothpicks and D-toothpicks after n steps. A182839 (first differences) gives the number added at the n-th stage.
[It appears that for this sequence a classic toothpick is a line segment of length 1 that is parallel to the y-axis. A D-toothpick is a line segment of length sqrt(2) with slope +-1. D stands for diagonal. It also appears that classic toothpicks are not placed on the y-axis. - N. J. A. Sloane, Feb 06 2023]
From Omar E. Pol, Feb 17 2023: (Start)
This cellular automaton appears to be a version on the square grid of the first quadrant of the structure of A182840.
The rules are as follows:
- The elements (toothpicks and D-toothpicks) are connected at their ends.
- At each free end of the elements of the old generation two elements of the new generation must be connected.
- The toothpicks of length 1 must always be placed vertically, i.e. parallel to the Y-axis.
- The angle between a toothpick of length 1 and a D-toothpick of length sqrt(2) that share the same node must be 135 degrees, therefore the angle between two D-toothpicks that share the same node is 90 degrees.
As a result of these rules we can see that in the odd-indexed rows of the structure are placed only the toothpicks of length 1 and in the even-indexed rows of the structure are placed the D-toothpicks of length sqrt(2).
Apart from the trapezoids, pentagons and heptagons that are adjacent to the axes of the first quadrant it appears that there are only three types of polygons:
- Regular hexagons of area 4.
- Concave decagons (or concave 10-gons) of area 8.
- Concave dodecagons (or concave 12-gons) of area 12.
There are infinitely many of these polygons.
The structure shows a fractal-like behavior as we can see in other members of the family of toothpick cellular automata.
The structure has internal growth as some members of the mentioned family. (End)

			We start at stage 0 with no toothpicks.
At stage 1 we place a D-toothpick [(0,1),(1,2)], so a(1)=1.
At stage 2 we place a toothpick [(1,2),(1,3)] and a D-toothpick [(1,2),(2,1)], so a(2)=1+2=3.
At stage 3 we place 4 elements: a D-toothpick [(1,3),(0,4)], a D-toothpick [(1,3),(2,4)], a D-toothpick [(2,1),(3,2)] and a toothpick [(2,1),(2,0)], so a(3)=3+4=7. Etc.
The first hexagon appears in the structure after 4 stages.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of a(32) = 549
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to toothpick sequences

Cf. A139250, A153000, A161206, A170888, A172308, A182632, A182634, A182839, A182840, A187212, A194444, A220524, A233970, A267458, A267694, A267698.

See A360501 and A360512 for another hexagonal net built on the square grid. - N. J. A. Sloane, Feb 09 2023

Conjecture: a(n) = (A182840(n+1) + A267458(n+1) - 2)/4. - Omar E. Pol, Feb 10 2023

Partially edited by N. J. A. Sloane, Feb 06 2023

a(19)-a(41) from Omar E. Pol, Feb 06 2023

A187216 Q-toothpick sequence starting with two opposite Q-toothpicks centered at the same grid point.

Original entry on oeis.org

0, 2, 8, 16, 30, 52, 82, 104, 142, 196, 266, 288, 326, 380, 450, 504, 606, 756, 890, 912, 950, 1004, 1074, 1128, 1230, 1380, 1514, 1568, 1670, 1820, 1986, 2168, 2494, 2900, 3162, 3184, 3222, 3276, 3346, 3400, 3502, 3652, 3786, 3840, 3942, 4092, 4258, 4440

Offset: 0

Omar E. Pol, Mar 30 2011

nonn

The sequence gives the number of Q-toothpicks in the structure after n-th stage.
A187217 (the first differences) gives the number of Q-toothpicks added at n-th stage.
Note that in the Q-toothpick structure sometimes there is also an internal growth of Q-toothpicks.
For more information see A187210.

			On the infinite square grid at stage 0 we start with no Q-toothpicks.
At stage 1 we place two opposite Q-toothpicks centered at (0,0). One of the Q-toothpicks lies on the first quadrant with its endpoints at (0,1) and (1,0). The other Q-toothpick lies on the third quadrant with its endpoints at (0,-1) and (-1,0). So a(1) = 2. There are 4 exposed endpoints.
At stage 2 we place 6 Q-toothpicks, so a(2) = 2+6 = 8.
At stage 3 we place 8 Q-toothpicks, so a(3) = 8+8 = 16.
At stage 4 we place 14 Q-toothpicks, so a(4) = 16+14 = 30.
After 4 stages in the Q-toothpick structure there are 1 circle, 2 "heads" and 12 exposed endpoints.

Nathaniel Johnston, Table of n, a(n) for n = 0..200
Nathaniel Johnston, C program for computing terms
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Nathaniel Johnston, The Q-Toothpick Cellular Automaton
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A139250, A160120, A160164, A187210, A187212, A187217, A187220.

a(15) - a(47) from Nathaniel Johnston, Apr 15 2011

A282470 Q-toothpick sequence with Q-toothpicks of radius 1 and 2 (see Comments for precise definition).

Original entry on oeis.org

0, 1, 9, 16, 40, 62, 102, 124, 204, 258, 338, 360, 440, 494, 606, 676, 916, 1050, 1194, 1216, 1296, 1350, 1462, 1532, 1772, 1906, 2082, 2152, 2392, 2542, 2878, 3124, 3844, 4170, 4442, 4464, 4544, 4598, 4710, 4780, 5020, 5154, 5330, 5400, 5640, 5790, 6126, 6372, 7092, 7418, 7722, 7792, 8032, 8182, 8518

Offset: 0

Omar E. Pol, Feb 16 2017

nonn

For the construction of this sequence we use the same the rules of A187210 (the Q-toothpick sequence) except that for the even-indexed generations here we use Q-toothpicks of radius 2, not 1.
The result is that the structure looks like an arrangement of ovals.
On the infinite square grid at stage 0 we start with no Q-toothpicks, so a(0) = 0.
For n >= 1, a(n) is the ratio between the total length of the lines of the structure after n-th stages and the length of a single Q-toothpick of radius 1.
A187210(n) gives the total number of Q-toothpicks in the structure after n-th stages.
A187211(n) gives the number of Q-toothpicks added at n-th stage.
Note that since the radius of the Q-toothpicks can be two distincts numbers so we can write an infinite number of sequences from cellular automata of this kind.

Cf. A282471 (essentially the first differences).
Cf. A187210 (Q-toothpick sequence).
Cf. A139250, A187212, A267694, A267698.

cp's OEIS Frontend

A187213 Number of Q-toothpicks added at n-th stage to the structure of A187212.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A187214 Number of gulls (or G-toothpicks) added at n-th stage in the first quadrant of the gullwing structure of A187212.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A139250 Toothpick sequence (see Comments lines for definition).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A187210 Q-toothpick sequence (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A182838 H-toothpick sequence in the first quadrant starting with a D-toothpick placed on the diagonal [(0,1), (1,2)] (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A187216 Q-toothpick sequence starting with two opposite Q-toothpicks centered at the same grid point.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A282470 Q-toothpick sequence with Q-toothpicks of radius 1 and 2 (see Comments for precise definition).

Views

Author

Keywords

Comments

Links

Crossrefs