A147562 -id:A147562 - cp's OEIS frontend

A139250 Toothpick sequence (see Comments lines for definition).

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

A160120 Y-toothpick sequence (see Comments lines for definition).

Original entry on oeis.org

0, 1, 4, 7, 16, 19, 28, 37, 58, 67, 76, 85, 106, 121, 142, 169, 220, 247, 256, 265, 286, 301, 322, 349, 400, 433, 454, 481, 532, 583, 640, 709, 826, 907, 928, 937, 958, 973, 994, 1021, 1072, 1105, 1126, 1153, 1204, 1255, 1312, 1381, 1498, 1585, 1618, 1645

Offset: 0

Omar E. Pol, May 02 2009

nonn

A Y-toothpick (or Y-shaped toothpick) is formed from three toothpicks of length 1, like a star with three endpoints and only one middle-point.
On the infinite triangular grid, we start at round 0 with no Y-toothpicks.
At round 1 we place a Y-toothpick anywhere in the plane.
At round 2 we add three more Y-toothpicks. After round 2, in the structure there are three rhombuses and a hexagon.
At round 3 we add three more Y-toothpicks.
And so on ... (see illustrations).
The sequence gives the number of Y-toothpicks after n rounds. A160121 (the first differences) gives the number added at the n-th round.
The Y-toothpick pattern has a recursive, fractal (or fractal-like) structure.
Note that, on the infinite triangular grid, a Y-toothpick can be represented as a polyedge with three components. In this case, at the n-th round, the structure is a polyedge with 3*a(n) components.
This structure is more complex than the toothpick structure of A139250. For example, at some rounds we can see inward growth.
The structure contains distinct polygons which have side length equal to 1.
Observation: It appears that the region of the structure where all grid points are covered is formed only by three distinct polygons:
- Triangles
- Rhombuses
- Concave-convex hexagons
Holes in the structure: Also, we can see distinct concave-convex polygons which contains a region where there are no grid points that are covered, for example:
- Decagons   (with  1 non-covered grid point)
- Dodecagons (with  4 non-covered grid points)
- 18-gons    (with  7 non-covered grid points)
- 30-gons    (with 26 non-covered grid points)
- ...
Observation: It appears that the number of distinct polygons that contain non-covered grid points is infinite.
This sequence appears to be related to powers of 2. For example:
Conjecture: It appears that if n = 2^k, k>0, then, between the other polygons, there appears a new centered hexagon formed by three rhombuses with side length = 2^k/2 = n/2.
Conjecture: Consider the perimeter of the structure. It appears that if n = 2^k, k>0, then the structure is a triangle-shaped polygon with A000225(k)*6 sides and a half toothpick in each vertice of the "triangle".
Conjecture: It appears that if n = 2^k, k>0, then the ratio of areas between the Y-toothpick structure and the unitary triangle is equal to A006516(k)*6.
See the entry A139250 for more information about the growth of "standard" toothpicks.
See also A160715 for another version of this structure but without internal growth of Y-toothpicks. [Omar E. Pol, May 31 2010]
For an alternative visualization replace every single toothpick with a rhombus, or in other words, replace every Y-toothpick with the "three-diamond" symbol, so we have a cellular automaton in which a(n) gives the total number of "three-diamond" symbols after n-th stage and A160167(n) counts the total number of "ON" diamonds in the structure after n-th stage. See also A253770. - Omar E. Pol, Dec 24 2015
The behavior is similar to A153006 (see the graph). - Omar E. Pol, Apr 03 2018

JungHwan Min, Table of n, a(n) for n = 0..5000
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.]
David Applegate, The movie version
Ayliean McDonald, Y-toothpick fractal, Twitter video (2021).
Olbaid Fractalium, Toothpick sequence Part 2, Youtube video (2023).
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Illustration of the structure after 17 stages
Omar E. Pol, Illustration of the structure after 34 stages, from Applegate's movie version.
Omar E. Pol, Illustration: Fractal recursion, general step. (1)
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 toothpicks)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to toothpick sequences
Index entries for sequences related to cellular automata

Toothpick sequence: A139250.

Cf. A000079, A000225, A006516, A147562, A153006, A160121, A160123, A160715, A161206, A161328, A161330, A161430, A173066, A173068, A253770.

YTPFunc[lis_, step_] := With[{out = Extract[lis, {{1, 2}, {2, 1}, {-1, -1}}], in = lis[[2, 2]]}, Which[in == 0 && Count[out, 2] >= 2, 1, in == 0 && Count[out, 2] == 1, 2, True, in]]; A160120[0] = 0; A160120[n_] := With[{m = n - 1}, Count[CellularAutomaton[{YTPFunc, {}, {1, 1}}, {{{2}}, 0}, {{{m}}}], 2, 2]] (* JungHwan Min, Jan 28 2016 *)
A160120[0] = 0; A160120[n_] := With[{m = n - 1}, Count[CellularAutomaton[{435225738745686506433286166261571728070, 3, {{-1, 0}, {0, -1}, {0, 0}, {1, 1}}}, {{{2}}, 0}, {{{m}}}], 2, 2]] (* JungHwan Min, Jan 28 2016 *)

More terms from David Applegate, Jun 14 2009, Jun 18 2009

A151723 Total number of ON states after n generations of cellular automaton based on hexagons.

Original entry on oeis.org

0, 1, 7, 13, 31, 37, 55, 85, 127, 133, 151, 181, 235, 289, 331, 409, 499, 505, 523, 553, 607, 661, 715, 817, 967, 1069, 1111, 1189, 1327, 1489, 1603, 1789, 1975, 1981, 1999, 2029, 2083, 2137, 2191, 2293, 2443, 2545, 2599, 2701, 2875, 3097, 3295

Offset: 0

David Applegate and N. J. A. Sloane, Jun 13 2009

nonn

Analog of A151725, but here we are working on the triangular lattice (or the A_2 lattice) where each hexagonal cell has six neighbors.
A cell is turned ON if exactly one of its six neighbors is ON. An ON cell remains ON forever.
We start with a single ON cell.
It would be nice to find a recurrence for this sequence!
Has a behavior similar to A182840 and possibly to A182632. - Omar E. Pol, Jan 15 2016

S. M. Ulam, On some mathematical problems connected with patterns of growth of figures, pp. 215-224 of R. E. Bellman, ed., Mathematical Problems in the Biological Sciences, Proc. Sympos. Applied Math., Vol. 14, Amer. Math. Soc., 1962 (see Example 6, page 224).

N. J. A. Sloane, Table of n, a(n) for n = 0..4095 [First 1026 terms from David Applegate and N. J. A. Sloane]
David Applegate, The movie version
David Applegate and N. J. A. Sloane, Table of n, A151724(n), A151723(n) for n = 0..1025
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.]
Bradley Klee, Log-periodic coloring, over the half-hexagon tiling.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021

Cf. A147562, A151724, A151725, A161206, A161644, A169779, A169780, A170898, A170905, A182632, A182840, A256536, A256537.

A151723[0] = 0; A151723[n_] := Total[CellularAutomaton[{10926, {2, {{2, 2, 0}, {2, 1, 2}, {0, 2, 2}}}, {1, 1}}, {{{1}}, 0}, {{{n - 1}}}], 2]; Array[A151723, 47, 0](* JungHwan Min, Sep 01 2016 *)
A151723L[n_] := Prepend[Total[#, 2] & /@ CellularAutomaton[{10926, {2, {{2, 2, 0}, {2, 1, 2}, {0, 2, 2}}}, {1, 1}}, {{{1}}, 0}, n - 1], 0]; A151723L[46] (* JungHwan Min, Sep 01 2016 *)

a(n) = 6*A169780(n) - 6*n + 1 (this is simply the definition of A169780).
a(n) = 1 + 6*A169779(n-2), n >= 2. - Omar E. Pol, Mar 19 2015
It appears that a(n) = a(n-2) + 3*(A256537(n) - 1), n >= 3. - Omar E. Pol, Apr 04 2015

Edited by N. J. A. Sloane, Jan 10 2010

A048645 Integers with one or two 1-bits in their binary expansion.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, 20, 24, 32, 33, 34, 36, 40, 48, 64, 65, 66, 68, 72, 80, 96, 128, 129, 130, 132, 136, 144, 160, 192, 256, 257, 258, 260, 264, 272, 288, 320, 384, 512, 513, 514, 516, 520, 528, 544, 576, 640, 768, 1024, 1025, 1026, 1028, 1032

Offset: 1

Antti Karttunen, Jul 14 1999

Apart from initial 1, sums of two not necessarily distinct powers of 2.
4 does not divide C(2s-1,s) (= A001700[ s ]) if and only if s=a(n).
Possible number of sides of a regular polygon such that there exists a triangulation where each triangle is isosceles. - Sen-peng Eu, May 07 2008
Also numbers n such that n!/2^(n-2) is an integer. - Michel Lagneau, Mar 28 2011
It appears these are also the indices of the terms that are shared by the cellular automata of A147562, A162795, A169707. - Omar E. Pol, Feb 21 2015
Numbers with binary weight 1 or 2. - Omar E. Pol, Feb 22 2015

			From _Omar E. Pol_, Feb 18 2015: (Start)
Also, written as a triangle T(j,k), k >= 1, in which row lengths are the terms of A028310:
   1;
   2;
   3,  4;
   5,  6,  8;
   9, 10, 12, 16;
  17, 18, 20, 24, 32;
  33, 34, 36, 40, 48, 64;
  65, 66, 68, 72, 80, 96, 128;
  ...
It appears that column 1 is A094373.
It appears that the right border gives A000079.
It appears that the first differences in every row that contains at least two terms give the first h-1 powers of 2, where h is the length of the row.
(End)

Reinhard Zumkeller, Rows n = 1..100 of triangle, flattened
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints.org (2025).
Michael P. Connolly, Probabilistic rounding error analysis for numerical linear algebra, Ph. D. Thesis, Univ. Manchester (UK, 2022). See p. 55.
USA Mathematical Olympiad, Problem 4, 2008.
Eric Weisstein's World of Mathematics, Automatic Set.
Eric Weisstein's World of Mathematics, Binomial Coefficient.
Index entries for sequences related to cellular automata.
Index to sequences related to Olympiads and other Mathematical competitions.

Cf. A018900, A048623, A046097, A169707, A147562, A162795, A003056, A002262, A094373, A028310, A179951.

import Data.List (insert)
a048645 n k = a048645_tabl !! (n-1) !! (k-1)
a048645_row n = a048645_tabl !! (n-1)
a048645_tabl = iterate (\xs -> insert (2 * head xs + 1) $ map ((* 2)) xs) [1]
a048645_list = concat a048645_tabl
-- Reinhard Zumkeller, Dec 19 2012

lincom:=proc(a,b,n) local i,j,s,m; s:={}; for i from 0 to n do for j from 0 to n do m:=a^i+b^j; if m<=n then s:={op(s),m} fi od; od; lprint(sort([op(s)])); end: lincom(2,2,1000); # Zerinvary Lajos, Feb 24 2007

Select[Range[2000], 1 <= DigitCount[#, 2, 1] <= 2&] (* Jean-François Alcover, Mar 06 2016 *)

isok(n) = my(hw = hammingweight(n)); (hw == 1) || (hw == 2); \\ Michel Marcus, Mar 06 2016

a(n) = if(n <= 2, return(n), n-=2); my(c = (sqrtint(8*n + 1) - 1) \ 2); 1 << c + 1 << (n - binomial(c + 1, 2)) \\ David A. Corneth, Jan 02 2019

nxt(n) = msb = 1 << logint(n, 2); if(n == msb, n + 1, t = n - msb; n + t) \\ David A. Corneth, Jan 02 2019

def ok(n): return 1 <= bin(n)[2:].count('1') <= 2
print([k for k in range(1033) if ok(k)]) # Michael S. Branicky, Jan 22 2022

from itertools import count, islice
def agen(): # generator of terms
    for d in count(0):
        msb = 2**d
        yield msb
        for lsb in range(d):
            yield msb + 2**lsb
print(list(islice(agen(), 60))) # Michael S. Branicky, Jan 22 2022

from math import isqrt, comb
def A048645(n): return (1<<(m:=isqrt(n-1<<3)+1>>1)-1)+(1<<(n-2-comb(m,2))) if n>1 else 1 # Chai Wah Wu, Oct 30 2024

a(0) = 1, a(n) = (2^(trinv(n-1)-1) + 2^((n-1)-((trinv(n-1)*(trinv(n-1)-1))/2))), i.e., 2^A003056(n) + 2^A002262(n-1) (the latter sequence contains the definition of trinv).
Let Theta = Sum_{k >= 0} x^(2^k). Then Sum_{n>=1} x^a(n) = (Theta^2 + Theta + x)/2. - N. J. A. Sloane, Jun 23 2009
As a triangle, for n > 1, 1 < k <= n: T(n,1) = A173786(n-2,n-2) and T(n,k) = A173786(n-1,k-2). - Reinhard Zumkeller, Feb 28 2010
It appears that A147562(a(n)) = A162795(a(n)) = A169707(a(n)). - Omar E. Pol, Feb 19 2015
Sum_{n>=1} 1/a(n) = 2 + A179951. - Amiram Eldar, Jan 22 2022

A160239 Number of "ON" cells in a 2-dimensional cellular automaton ("Fredkin's Replicator") evolving according to the rule that a cell is ON in a given generation if and only if there was an odd number of ON cells among the eight nearest neighbors in the preceding generation, starting with one ON cell.

Original entry on oeis.org

1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728, 8, 64, 64, 192, 64, 512, 192, 896, 64, 512, 512, 1536, 192, 1536, 896, 3328, 24, 192, 192, 576, 192, 1536, 576, 2688, 112, 896, 896, 2688, 416, 3328, 1728, 6784

Offset: 0

John W. Layman, May 05 2009

This is the odd-rule cellular automaton defined by OddRule 757 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

The partial sums are in A245542, in which the structure also looks like an irregular stepped pyramid. - Omar E. Pol, Jan 29 2015

			From _Omar E. Pol_, Jul 22 2014 (Start):
Written as an irregular triangle in which row lengths is A011782 the sequence begins:
1;
8;
8, 24;
8, 64, 24, 112;
8, 64, 64, 192, 24, 192, 112, 416;
8, 64, 64, 192, 64, 512, 192, 896, 24, 192, 192, 576, 112, 896, 416, 1728;
8, 64, 64, 192, 64, 512, 192, 896, 64, 512, 512, 1536, 192, 1536, 896, 3328, 24, 192, 192, 576, 192, 1536, 576, 2688, 112, 896, 896, 2688, 416, 3328, 1728, 6784;
(End)
Right border gives A246030. - _Omar E. Pol_, Jan 29 2015 [This is simply a restatement of the theorem that this sequence is the Run Length Transform of A246030. - _N. J. A. Sloane_, Jan 29 2015]
.
From _Omar E. Pol_, Mar 18 2015 (Start):
Also, the sequence can be written as an irregular tetrahedron as shown below:
1;
..
8;
..
8;
24;
.........
8,    64;
24;
112;
...................
8,    64,  64, 192;
24,  192;
112;
416;
.....................................
8,    64,  64, 192, 64, 512,192, 896;
24,  192, 192, 576;
112, 896;
416;
1728;
.......................................................................
8,    64,  64, 192, 64, 512,192, 896,64,512,512,1536,192,1536,896,3328;
24,  192, 192, 576,192,1536,576,2688;
112, 896, 896,2688;
416,3328;
1728;
6784;
...
Apart from the initial 1, we have that T(s,r,k) = T(s+1,r,k). On the other hand, it appears that the configuration of ON cells of T(s,r,k) is also the central part of the configuration of ON cells of T(s+1,r+1,k).
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
Charles R Greathouse IV, Compact illustration of generations 0..17
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, Enlarged illustration of first 16 generations (pdf).
N. J. A. Sloane, Illustration for a(15) = 416 (png).
N. J. A. Sloane, Illustration for a(15) = 416 (pdf).
N. J. A. Sloane, Illustration for a(31) = 1728.
N. J. A. Sloane, Illustration for a(63) = 6784.
N. J. A. Sloane, Illustration for a(127) = 27392 (tiff).
N. J. A. Sloane, Illustration for a(127) = 27392 (png).
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 13.
Index entries for sequences related to cellular automata

Cf. A122108, A147562, A164032, A245180 (gives a(n)/8, n>=2).

Cf. also A245542 (Partial sums), A245543, A083424, A245562, A246030, A254731 (an "even-rule" version).

import Data.List (transpose)
a160239 n = a160239_list !! n
a160239_list = 1 : (concat $
   transpose [a8, hs, zipWith (+) (map (* 2) hs) a8, tail a160239_list])
   where a8 = map (* 8) a160239_list;
         hs = h a160239_list; h (_:x:xs) = x : h xs
-- Reinhard Zumkeller, Feb 13 2015

# From N. J. A. Sloane, Jan 19 2015:
f:=proc(n) option remember;
if n=0 then RETURN(1);
elif n mod 2 = 0 then RETURN(f(n/2))
elif n mod 4 = 1 then RETURN(8*f((n-1)/4))
else RETURN(f(n-2)+2*f((n-1)/2)); fi;
end;
[seq(f(n),n=0..255)];

A160239[n_] :=
CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, {{n}}][[1]] // Total@*Total (* Charles R Greathouse IV, Aug 21 2014 *)
ArrayPlot /@ CellularAutomaton[{52428, {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}}, {1, 1}}, {{{1}}, 0}, 30] (* Charles R Greathouse IV, Aug 21 2014 *)

A160239=[];a(n)={if(n>#A160239,A160239=concat(A160239,vector(n-#A160239)),n||return(1);A160239[n]&&return(A160239[n]));A160239[n]=if(bittest(n,0),if(bittest(n,1),a(n-2)+2*a(n\2),a(n\4)*8),a(n\2))} \\ M. F. Hasler, May 10 2016

a(0) = 1; a(2t)=a(t), a(4t+1)=8*a(t), a(4t+3)=2*a(2t+1)+8*a(t) for t >= 0. (Conjectured by Hrothgar, Jul 11 2014; proved by N. J. A. Sloane, Oct 04 2014.)
For n >= 2, a(n) = 8^r * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n=7 = 111 in binary, so r=1, i=3, R(3) = A083424(2) = 14, and so a(7) = 8^1*14 = 112. That is, this sequence is the Run Length Transform of A246030. - N. J. A. Sloane, Oct 04 2014
The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g. 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Aug 25 2014

Offset changed to 1 by Hrothgar, Jul 11 2014

Offset reverted to 0 by N. J. A. Sloane, Jan 19 2015

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Original entry on oeis.org

1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, 256, 259, 268, 277, 304, 313, 340, 367, 448, 457, 484, 511, 592, 619, 700, 781, 1024, 1027, 1036, 1045, 1072, 1081, 1108, 1135, 1216, 1225, 1252, 1279, 1360, 1387, 1468, 1549, 1792, 1801, 1828, 1855

Offset: 0

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

Partial sums of A048883. - David Applegate, Jun 11 2009
From Gary W. Adamson, Aug 26 2016: (Start)
The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
  1, 0, 0, 0, 0, 0, ...
  4, 0, 0, 0, 0, 0, ...
  3, 1, 0, 0, 0, 0, ...
  0, 4, 0, 0, 0, 0, ...
  0, 3, 1, 0, 0, 0, ...
  0, 0, 4, 0, 0, 0, ...
  0, 0, 3, 1, 0, 0, ...
  ...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Applegate, The movie version
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 31-32.
Tanya Khovanova and Joshua Xiong, Nim Fractals, arXiv:1405.594291 [math.CO], 2014 and J. Int. Seq. 17 (2014) # 14.7.8.
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
Omar E. Pol, Illustration of initial terms: Fig. 1. Neighbors of the vertices, Fig. 2. Overlapping squares, Fig. 3. One-step bishop, (Nov 08 2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.

Cf. A000120, A006046 (Sum 2^wt(n)), A116520, A130667, A147562, A151920, A151922, A160410, A160412, A360189.

a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
-- Reinhard Zumkeller, Apr 18 2012

u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset

f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)

def a(n):  # formula version, n=10^10000 takes ~1 second
    if n == 0:
        return 1
    msb = 1 << (n.bit_length() - 1)
    return msb**2 + 3 * a(n-msb) # Stefan Pochmann, Mar 15 2023

def a(n):  # optimized, n=10^50000 takes ~1 second
    n += 1
    total = 0
    power3 = 1
    while n:
        log = n.bit_length() - 1
        total += power3 << (2*log)
        n -= 1 << log
        power3 *= 3
    return total # Stefan Pochmann, Mar 15 2023

With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
a(n) = (A147562(n+1) - 1)*3/4 + 1. - Omar E. Pol, Nov 08 2009
a(n) = A160410(n+1)/4. - Omar E. Pol, Nov 12 2009
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
r(x)* r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
For asymptotics see the discussion in the comments in A006046. - N. J. A. Sloane, Mar 11 2021
a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - Alois P. Heinz, Mar 06 2023
a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - Stefan Pochmann, Mar 15 2023

Simpler definition (and new offset) from David Applegate, Jun 11 2009

Lower limit of sum in definition changed from 1 to 0 by Robert G. Wilson v, Jun 28 2010

A296612 Square array read by antidiagonals upwards: T(n,k) equals k times the number of compositions (ordered partitions) of n, with n >= 0 and k >= 1.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 4, 4, 3, 4, 8, 8, 6, 4, 5, 16, 16, 12, 8, 5, 6, 32, 32, 24, 16, 10, 6, 7, 64, 64, 48, 32, 20, 12, 7, 8, 128, 128, 96, 64, 40, 24, 14, 8, 9, 256, 256, 192, 128, 80, 48, 28, 16, 9, 10, 512, 512, 384, 256, 160, 96, 56, 32, 18, 10, 11, 1024, 1024, 768, 512, 320, 192, 112, 64, 36, 20, 11, 12

Offset: 0

Omar E. Pol, Jan 04 2018

Also, at least for the first five columns, column k gives the row lengths of the irregular triangles of the first differences of the total number of elements in the structure of some cellular automata. Indeed, the study of the structure and the behavior of the toothpick cellular automaton on triangular grid (A296510), and other C.A. of the same family, reveals that some cellular automata that have recurrent periods can be represented by irregular triangles (of first differences) whose row lengths are the terms of A011782 multiplied by k (instead of powers of 2), where k is the length of an internal cycle. This internal cycle is called here "word" of a cellular automaton (see examples).

			The corner of the square array begins:
    1,   2,   3,    4,    5,    6,    7,    8,    9,   10, ...
    1,   2,   3,    4,    5,    6,    7,    8,    9,   10, ...
    2,   4,   6,    8,   10,   12,   14,   16,   18,   20, ...
    4,   8,  12,   16,   20,   24,   28,   32,   36,   40, ...
    8,  16,  24,   32,   40,   48,   56,   64,   72,   80, ...
   16,  32,  48,   64,   80,   96,  112,  128,  144,  160, ...
   32,  64,  96,  128,  160,  192,  224,  256,  288,  320, ...
   64, 128, 192,  256,  320,  384,  448,  512,  576,  640, ...
  128, 256, 384,  512,  640,  768,  896, 1024, 1152, 1280, ...
  256, 512, 768, 1024, 1280, 1536, 1792, 2048, 2304, 2560, ...
...
For k = 1 consider A160120, the Y-toothpick cellular automaton, which has word "a", so the structure of the irregular triangle of the first differences (A160161) is as follows:
a;
a;
a,a;
a,a,a,a;
a,a,a,a,a,a,a,a;
...
An associated sound to the animation of this cellular automaton could be (tick), (tick), (tick), ...
The row lengths of the above triangle are the terms of A011782, equaling the column 1 of the square array: 1, 1, 2, 4, 8, ...
.
For k = 2 consider A139250, the normal toothpick C.A. which has word "ab", so the structure of the irregular triangle of the first differences (A139251) is as follows:
a,b;
a,b;
a,b,a,b;
a,b,a,b,a,b,a,b;
a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b;
...
An associated sound to the animation could be (tick, tock), (tick, tock), ..., the same as the ticking clock sound.
The row lengths of the above triangle are the terms of A011782 multiplied by 2, equaling the column 2 of the square array: 2, 2, 4, 8, 16, ...
.
For k = 3 consider A296510, the toothpicks C.A. on triangular grid, which has word "abc", so the structure of the irregular triangle of the first differences (A296511) is as follows:
a,b,c;
a,b,c;
a,b,c,a,b,c;
a,b,c,a,b,c,a,b,c,a,b,c;
a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c;
...
An associated sound to the animation could be (tick, tock, tack), (tick, tock, tack), ...
The row lengths of the above triangle are the terms of A011782 multiplied by 3, equaling the column 3 of the square array: 3, 3, 6, 12, 24, ...
.
For k = 4 consider A299476, the toothpick C.A. on triangular grid with word "abcb", so the structure of the irregular triangle of the first differences (A299477) is as follows:
a,b,c,b;
a,b,c,b;
a,b,c,b,a,b,c,b;
a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b;
a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b,a,b,c,b;
...
An associated sound to the animation could be (tick, tock, tack, tock), (tick, tock, tack, tock), ...
The row lengths of the above triangle are the terms of A011782 multiplied by 4, equaling the column 4 of the square array: 4, 4, 8, 16, 32, ...
.
For k = 5 consider A299478, the toothpick C.A. on triangular grid with word "abcbc", so the structure of the irregular triangle of the first differences (A299479) is as follows:
a,b,c,b,c;
a,b,c,b,c;
a,b,c,b,c,a,b,c,b,c;
a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c;
a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c,a,b,c,b,c;
...
An associated sound to the animation could be (tick, tock, tack, tock, tack), (tick, tock, tack, tock, tack), ...
The row lengths of the above triangle are the terms of A011782 multiplied by 5, equaling the column 5 of the square array: 5, 5, 10, 20, 40, ...

Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.
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. A011782, A147562, A147582, A139250, A139251, A160160, A160161, A296510, A296511, A296610, A296611, A299476, A299477, A299478, A299479.

T(n,k) = k*A011782(n), with n >= 0 and k >= 1.

A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

Original entry on oeis.org

1, 5, 9, 21, 25, 37, 57, 85, 89, 101, 121, 149, 169, 213, 281, 341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521

Offset: 1

N. J. A. Sloane, Apr 17 2010

Square grid, 4 neighbors per cell (N, E, S, W cells), turn ON iff exactly 1 or 3 neighbors are ON; once ON, cells stay ON.
The terms agree with those of A246335 for n <= 11, although the configurations are different starting at n = 7. - N. J. A. Sloane, Sep 21 2014
Offset 1 is best for giving a formula for a(n), although the Maple and Mathematica programs index the states starting at state 0.
It appears that this shares infinitely many terms with both A162795 and A147562, see Formula section and Example section. - Omar E. Pol, Feb 19 2015

			Divides naturally into blocks of sizes 1,2,4,8,16,...:
1,
5, 9,
21, 25, 37, 57,
85, 89, 101, 121, 149, 169, 213, 281, <- terms 8 through 15
341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241,
1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521, ...
From _Omar E. Pol_, Feb 18 2015: (Start)
Also, written as an irregular triangle T(j,k), k>=1, in which the row lengths are the terms of A011782:
1;
5;
9,   21;
25,  37,   57,  85;
89,  101, 121, 149, 169, 213, 281, 341;
345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365;
The right border gives the positive terms of A002450.
It appears that T(j,k) = A162795(j,k) = A147562(j,k), if k is a power of 2, for example: it appears that the three mentioned triangles only share the elements from the columns 1, 2, 4, 8, 16, ...
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

N. J. A. Sloane and Vincenzo Librandi, Table of n, a(n) for n = 1..513, computed from the definition, not using the conjectured formula. [The first 200 terms were found by _Vincenzo Librandi_]
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.], arXiv:1004.3036 [math.CO].
N. J. A. Sloane, Table of n, a(n) for n=1..8192 assuming the recurrence is correct. Note that these terms are merely conjectures.
N. J. A. Sloane, Illustration of first 24 generations
N. J. A. Sloane, Illustration of first 24 generations of the NW-NE-SE-SW version of this CA
N. J. A. Sloane, Illustration of generation 7 of the NW-NE-SE-SW version of this CA (containing a(7) = 57 ON cells)
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A169708 (first differences), A147562, A147582, A169648, A169649, A169709, A169710, A246333, A246334, A246335, A246336, A253098 (partial sums).
Cf. also A162795, A150552, A160104, A170903, A048645, A187200.
See A253088 for the analogous CA using Rule 750 and a 9-celled neighborhood.

(Maple program that uses the actual definition of the automaton, rather than the (conjectured) formula, from N. J. A. Sloane, Feb 15 2015):
# Count terms in a polynomial:
C := f->`if`(type(f, `+`), nops(f), 1);
# Replace all nonzero coeffts by 1:
bool := proc(f) local ix, iy, f2, i, t1, t2, A;
f2:=expand(f);
if whattype(f) = `+` then
t1:=nops(f2); A:=0;
for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);
A:=A+x^ix*y^iy; od: A;
else ix:=degree(f2, x); iy:=degree(f2, y); x^ix*y^iy;
fi;
end;
# a loop that produces M steps of A169707 and A169708:
M:=20;
F:=x*y+x/y+1/x*y+1/x/y mod 2;
GG[0]:=1;
for n from 1 to M do dd[n]:=expand(F*GG[n-1]) mod 2;
GG[n]:=bool(GG[n-1]+dd[n]);
lprint(n,C(GG[n]), C(GG[n]-GG[n-1])); od:

Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 750, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 23]
(* The next two lines deal with the equivalent CA based on neighbors NW, NE, SE, SW. This is to facilitate the comparison with A246333 and A246335 *)
Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[{ 750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 23]

a(2^k + i) = (4^(k+1)-1)/3 + 4*A246336(i), for k >= 0, 0 <= i < 2^k. For example, if n = 15 = 2^3 + 7, so k=3, i=7, we have a(15) = (4^4-1)/3 + 4*A246336(7) = 85 + 4*49 = 281.
a(n) = 1 + 2*(A139250(n) - A160552(n)) = A160164(n) - A170903(n) = A187220(n) + 2*(A160552(n-1)). - Omar E. Pol, Feb 18 2015
It appears that a(n) = A162795(n) = A147562(n), if n is a member of A048645, otherwise a(n) > A162795(n) > A147562(n). - Omar E. Pol, Feb 19 2015
It appears that a(n) = 1 + 4*A255747(n-1). - Omar E. Pol, Mar 05 2015
It appears that a(n) = 1 + 4*(A139250(n-1) - (a(n-1) - 1)/4), n > 1. - Omar E. Pol, Jul 24 2015
It appears that a(2n) = 1 + 4*A162795(n). - Omar E. Pol, Jul 04 2017

Edited (added formula, illustration, etc.) by N. J. A. Sloane, Aug 30 2014

Offset changed to 1 by N. J. A. Sloane, Feb 09 2015

cp's OEIS Frontend

A272928 Partial sums of A147562.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A288775 Difference between the total number of toothpicks in the toothpick structure of A139250 that are parallel to the initial toothpick after n odd stages, and the total number of "ON" cells at n-th stage in the "Ulam-Warburton" two-dimensional cellular automaton of A147562.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A160120 Y-toothpick sequence (see Comments lines for definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A151723 Total number of ON states after n generations of cellular automaton based on hexagons.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A048645 Integers with one or two 1-bits in their binary expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Formula

Views

Author

Keywords

Comments

Examples