A160410 -id:A160410 - cp's OEIS frontend

A160414 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (same as A160410, but a(1) = 1, not 4).

0, 1, 9, 21, 49, 61, 97, 133, 225, 237, 273, 309, 417, 453, 561, 669, 961, 973, 1009, 1045, 1153, 1189, 1297, 1405, 1729, 1765, 1873, 1981, 2305, 2413, 2737, 3061, 3969, 3981, 4017, 4053, 4161, 4197, 4305, 4413, 4737, 4773, 4881, 4989, 5313, 5421, 5745

Offset: 0

Omar E. Pol, May 20 2009

The structure has a fractal behavior similar to the toothpick sequence A139250.
First differences: A161415, where there is an explicit formula for the n-th term.
For the illustration of a(24) = 1729 (the Hardy-Ramanujan number) see the Links section.

			From _Omar E. Pol_, Sep 24 2015: (Start)
With the positive terms written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
9;
21,    49;
61,    97,  133,  225;
237,  273,  309,  417,  453, 561,  669,  961;
...
Right border gives A060867.
This triangle T(n,k) shares with the triangle A256530 the terms of the column k, if k is a power of 2, for example both triangles share the following terms: 1, 9, 21, 49, 61, 97, 225, 237, 273, 417, 961, etc.
.
Illustration of initial terms, for n = 1..10:
.       _ _ _ _                       _ _ _ _
.      |  _ _  |                     |  _ _  |
.      | |  _|_|_ _ _ _ _ _ _ _ _ _ _|_|_  | |
.      | |_|  _ _     _ _   _ _     _ _  |_| |
.      |_ _| |  _|_ _|_  | |  _|_ _|_  | |_ _|
.          | |_|  _ _  |_| |_|  _ _  |_| |
.          |   | |  _|_|_ _ _|_|_  | |   |
.          |  _| |_|  _ _   _ _  |_| |_  |
.          | | |_ _| |  _|_|_  | |_ _| | |
.          | |_ _| | |_|  _  |_| | |_ _| |
.          |  _ _  |  _| |_| |_  |  _ _  |
.          | |  _|_| | |_ _ _| | |_|_  | |
.          | |_|  _| |_ _| |_ _| |_  |_| |
.          |   | | |_ _ _ _ _ _ _| | |   |
.          |  _| |_ _| |_   _| |_ _| |_  |
.       _ _| | |_ _ _ _| | | |_ _ _ _| | |_ _
.      |  _| |_ _|   |_ _| |_ _|   |_ _| |_  |
.      | | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _| | |
.      | |_ _| |                     | |_ _| |
.      |_ _ _ _|                     |_ _ _ _|
.
After 10 generations there are 273 ON cells, so a(10) = 273.
(End)

Paolo Xausa, Table of n, a(n) for n = 0..10000
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 the structure after 24th stage (contains 1729 ON cells)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A001235, A011541, A011782, A000225, A060867, A139250, A147562, A160117, A160118, A160410, A160412, A161415, A160720, A160727, A151725, A256530, A256534.

read("transforms") ; isA000079 := proc(n) if type(n,'even') then nops(numtheory[factorset](n)) = 1 ; else false ; fi ; end proc:
A048883 := proc(n) 3^wt(n) ; end proc:
A161415 := proc(n) if n = 1 then 1; elif isA000079(n) then 4*A048883(n-1)-2*n ; else 4*A048883(n-1) ; end if; end proc:
A160414 := proc(n) add( A161415(k),k=1..n) ; end proc: seq(A160414(n),n=0..90) ; # R. J. Mathar, Oct 16 2010

A160414list[nmax_]:=Accumulate[Table[If[n<2,n,4*3^DigitCount[n-1,2,1]-If[IntegerQ[Log2[n]],2n,0]],{n,0,nmax}]];A160414list[100] (* Paolo Xausa, Sep 01 2023, after R. J. Mathar *)

my(s=-1, t(n)=3^norml2(binary(n-1))-if(n==(1<Altug Alkan, Sep 25 2015

a(n) = 1 + 4*A219954(n), n >= 1. - M. F. Hasler, Dec 02 2012

a(2^k) = (2^(k+1) - 1)^2. - Omar E. Pol, Jan 05 2013

Edited by N. J. A. Sloane, Jun 15 2009 and Jul 13 2009

More terms from R. J. Mathar, Oct 16 2010

A161411 First differences of A160410.

Original entry on oeis.org

4, 12, 12, 36, 12, 36, 36, 108, 12, 36, 36, 108, 36, 108, 108, 324, 12, 36, 36, 108, 36, 108, 108, 324, 36, 108, 108, 324, 108, 324, 324, 972, 12, 36, 36, 108, 36, 108, 108, 324, 36, 108, 108, 324, 108, 324, 324, 972, 36, 108, 108, 324, 108, 324, 324, 972, 108, 324, 324

Offset: 1

Omar E. Pol, May 20 2009, Jun 13 2009, Jun 14 2009

The rows of the triangle in A147582 converge to this sequence.
Contribution from Omar E. Pol, Mar 28 2011 (Start):
a(n) is the number of cells turned "ON" at n-th stage of the cellular automaton of A160410.
a(n) is also the number of toothpicks added at n-th stage to the toothpick structure of A160410.
(End)

			If written as a triangle:
.4;
.12;
.12,36;
.12,36,36,108;
.12,36,36,108,36,108,108,324;

Paolo Xausa, Table of n, a(n) for n = 1..10000
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
Omar E. Pol, Illustration of initial terms (Neighbors of the vertices) [From _Omar E. Pol_, Nov 17 2009]

Cf. A139250, A139251, A160413, A160415, A160417.

Cf. A000079, A048883, A147582, A160410, A160414.

4*3^DigitCount[Range[0,100],2,1] (* Paolo Xausa, Sep 01 2023 *)

a(n) = A048883(n-1)*4.

Edited by David Applegate and N. J. A. Sloane, Jul 13 2009

A160428 Number of ON cells at n-th stage of three-dimensional version of the cellular automaton A160410, using cubes.

Original entry on oeis.org

0, 8, 64, 120, 512, 568, 960, 1352, 4096, 4152, 4544, 4936, 7680, 8072, 10816, 13560, 32768, 32824, 33216, 33608, 36352, 36744, 39488, 42232, 61440, 61832, 64576, 67320, 86528, 89272, 108480, 127688, 262144, 262200, 262592, 262984, 265728, 266120, 268864, 271608

Offset: 0

Omar E. Pol, Jun 01 2009

nonn

Michael De Vlieger, Table of n, a(n) for n = 0..1000
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.]
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, p. 33.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A139250, A160119, 160379, A160410, A160429, A161340, A161342.

a[n_] := 8*Sum[7^DigitCount[k, 2, 1], {k, 0, n - 1}]; Array[a, 40, 0] (* Michael De Vlieger, Nov 01 2022 *)

a(n) = 8 * Sum_{k=0..n-1} 7^A000120(k)

a(n) = 8 + 56 * Sum_{k=1..n-1} A151785(k) for n >= 1

Formulas and more terms from Nathaniel Johnston, Nov 13 2010

More terms from Michael De Vlieger, Nov 01 2022

A160799 Partial sums of A160410.

Original entry on oeis.org

0, 4, 20, 48, 112, 188, 300, 448, 704, 972, 1276, 1616, 2064, 2548, 3140, 3840, 4864, 5900, 6972, 8080, 9296, 10548, 11908, 13376, 15168, 16996, 18932, 20976, 23344, 25820, 28620, 31744, 35840, 39948, 44092, 48272, 52560, 56884, 61316, 65856

Offset: 1

Omar E. Pol, Jun 14 2009

nonn

Cf. A160410, A161411, A160807.

a(n)=4*sum(i=0, n-1, (n-i)*3^hammingweight(i)) \\ Charles R Greathouse IV, Aug 25 2016

More terms from Max Alekseyev, Dec 12 2011

A147562 Number of "ON" cells at n-th stage in the "Ulam-Warburton" two-dimensional cellular automaton.

Original entry on oeis.org

0, 1, 5, 9, 21, 25, 37, 49, 85, 89, 101, 113, 149, 161, 197, 233, 341, 345, 357, 369, 405, 417, 453, 489, 597, 609, 645, 681, 789, 825, 933, 1041, 1365, 1369, 1381, 1393, 1429, 1441, 1477, 1513, 1621, 1633, 1669, 1705, 1813, 1849, 1957, 2065, 2389, 2401, 2437, 2473

Offset: 0

N. J. A. Sloane, based on emails from Franklin T. Adams-Watters, R. J. Mathar and David W. Wilson, Apr 29 2009

Studied by Holladay and Ulam circa 1960. See Fig. 1 and Example 1 of the Ulam reference. - N. J. A. Sloane, Aug 02 2009.
Singmaster calls this the Ulam-Warburton cellular automaton. - N. J. A. Sloane, Aug 05 2009
On the infinite square grid, start with all cells OFF.
Turn a single cell to the ON state.
At each subsequent step, each cell with exactly one neighbor ON is turned ON, and everything that is already ON remains ON.
Here "neighbor" refers to the four adjacent cells in the X and Y directions.
Note that "neighbor" could equally well refer to the four adjacent cells in the diagonal directions, since the graph formed by Z^2 with "one-step rook" adjacencies is isomorphic to Z^2 with "one-step bishop" adjacencies.
Also toothpick sequence starting with a central X-toothpick followed by T-toothpicks (see A160170 and A160172). The sequence gives the number of polytoothpicks in the structure after n-th stage. - Omar E. Pol, Mar 28 2011
It appears that this sequence shares infinitely many terms with both A162795 and A169707, see Formula section and Example section. - Omar E. Pol, Feb 20 2015
It appears that the positive terms are also the odd terms (a bisection) of A151920. - Omar E. Pol, Mar 06 2015
Also, the number of active (ON, black) cells in the n-th stage of growth of two-dimensional cellular automaton defined by Wolfram's "Rule 558" or "Rule 686" based on the 5-celled von Neumann neighborhood. - Robert Price, May 10 2016
From Omar E. Pol, Mar 05 2019: (Start)
a(n) is also the total number of "hidden crosses" after 4*n stages in the toothpick structure of A139250, including the central cross, beginning to count the crosses when their nuclei are totally formed with 4 quadrilaterals.
a(n) is also the total number of "flowers with six petals" after 4*n stages in the toothpick structure of A323650.
Note that the location of the "nuclei of the hidden crosses" and the "flowers with six petals" in both toothpick structures is essentially the same as the location of the "ON" cells in the version "one-step bishop" of this sequence (see the illustration of initial terms, figure 2). (End)
This sequence has almost exactly the same graph as A187220, A162795, A169707 and A160164 which is twice A139250. - Omar E. Pol, Jun 18 2022

			If we label the generations of cells turned ON by consecutive numbers we get a rosetta cell pattern:
. . . . . . . . . . . . . . . . .
. . . . . . . . 4 . . . . . . . .
. . . . . . . 4 3 4 . . . . . . .
. . . . . . 4 . 2 . 4 . . . . . .
. . . . . 4 3 2 1 2 3 4 . . . . .
. . . . . . 4 . 2 . 4 . . . . . .
. . . . . . . 4 3 4 . . . . . . .
. . . . . . . . 4 . . . . . . . .
. . . . . . . . . . . . . . . . .
In the first generation, only the central "1" is ON, a(1)=1. In the next generation, we turn ON four "2", leading to a(2)=a(1)+4=5. In the third generation, four "3" are turned ON, a(3)=a(2)+4=9. In the fourth generation, each of the four wings allows three 4's to be turned ON, a(4)=a(3)+4*3=21.
From _Omar E. Pol_, Feb 18 2015: (Start)
Also, written as an irregular triangle T(j,k), j>=0, k>=1, in which the row lengths are the terms of A011782:
1;
5;
9,   21;
25,  37, 49, 85;
89, 101,113,149,161,197,233,341;
345,357,369,405,417,453,489,597,609,645,681,789,825,933,1041,1365;
...
The right border gives the positive terms of A002450.
(End)
It appears that T(j,k) = A162795(j,k) = A169707(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, ... - _Omar E. Pol_, Feb 20 2015

S. 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.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
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.]
Steven R. Finch, Toothpicks and Live Cells, July 21, 2015. [Cached copy, with permission of the author]
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, p. 31.
Bradley Klee, Log-periodic coloring of the first quadrant, over the chair tiling.
Omar E. Pol, Illustration of initial terms (Fig. 1: one-step rook - the current sequence), (Fig. 2: one-step bishop), (Fig. 3: overlapping squares), (Fig. 4: overlapping X-toothpicks), (2009), (Fig. 5: overlapping circles), (2010)
Omar E. Pol, Illustration of initial terms of A139250, A160120, A147562 (overlapping figures), (2009).
David Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7. Also scanned annotated cached copy, included with permission.
N. J. A. Sloane, Illustration of terms 0 through 9
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021
N. J. A. Sloane and Brady Haran, Terrific Toothpick Patterns, Numberphile video (2018).
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A000120, A139250, A147582 (number turned ON at n-th step), A147610, A130665, A151920, A151917, A160120, A160164, A160410, A160414, A162795, A169707, A187220, A246331, A323650.

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

A160720 Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition).

Original entry on oeis.org

0, 1, 5, 9, 21, 25, 37, 49, 77, 81, 93, 105, 133, 145, 173, 201, 261, 265, 277, 289, 317, 329, 357, 385, 445, 457, 485, 513, 573, 601, 661, 721, 845, 849, 861, 873, 901, 913, 941, 969, 1029, 1041, 1069, 1097, 1157, 1185, 1245, 1305, 1429, 1441, 1469, 1497

Offset: 0

Omar E. Pol, May 25 2009

nonn

We work on the vertices of the square grid Z^2, and define the neighbors of a cell to be the four closest cells along the diagonals.
We start at stage 0 with all cells in OFF state.
At stage 1, we turn ON a single cell at the origin.
Once a cell is ON it stays ON.
At each subsequent stage, a cell in turned ON if exactly one of its neighboring cells that are no further from the origin is ON.
The "no further from the origin" condition matters for the first time at stage 8, when only A160721(8) = 28 cells are turned ON, and a(8) = 77. In contrast, A147562(8) = 85, A147582(8) = 36.
This CA also arises as the cross-section in the (X,Y)-plane of the CA in A151776.
In other words, a cell is turned ON if exactly one of its vertices touches an exposed vertex of a ON cell of the previous generation. A special rule for this sequence is that every ON cell has only one vertex that should be considered not exposed: its nearest vertex to the center of the structure.
Analog to the "outward" version (A266532) of the Y-toothpick cellular automaton of A160120 on the triangular grid, but here we have ON cells on the square grid. See also the formula section. - Omar E. Pol, Jan 19 2016
This cellular automaton can be interpreted as the outward version of the Ulam-Warburton two-dimensional cellular automaton (see A147562). - Omar E. Pol, Jun 22 2017

			If we label the generations of cells turned ON by consecutive numbers we get the cell pattern shown below:
9...............9
.8.8.8.8.8.8.8.8.
..7...7...7...7..
.8.6.6.....6.6.8.
....5.......5....
.8.6.4.4.4.4.6.8.
..7...3...3...7..
.8...4.2.2.4...8.
........1........
.8...4.2.2.4...8.
..7...3...3...7..
.8.6.4.4.4.4.6.8.
....5.......5....
.8.6.6.....6.6.8.
..7...7...7...7..
.8.8.8.8.8.8.8.8.
9...............9

JungHwan Min, Table of n, a(n) for n = 0..5000
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.]
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, p. 30.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A139250, A147562, A159912, A160117, A160118, A160120, A160721, A160740, A147562, A160410, A160414, A160412, A160416, A160796, A266532, A267700.

cellOn := [[0,0]] : bbox := [0,0,0,0]: # llx, lly, urx, ury isOn := proc(x,y,L) local i ; for i in L do if op(1,i) = x and op(2,i) = y then RETURN(true) ; fi; od: RETURN(false) ; end: bb := proc(L) local mamin,i; mamin := [0,0,0,0] ; for i in L do mamin := subsop(1=min(op(1,mamin),op(1,i)),mamin) ; mamin := subsop(2=min(op(2,mamin),op(2,i)),mamin) ; mamin := subsop(3=max(op(1,mamin),op(1,i)),mamin) ; mamin := subsop(4=max(op(2,mamin),op(2,i)),mamin) ; od: mamin ; end: for gen from 2 to 80 do nGen := [] ; print(nops(cellOn)) ; for x from op(1,bbox)-1 to op(3,bbox)+1 do for y from op(2,bbox)-1 to op(4,bbox)+1 do # not yet in list? if not isOn(x,y,cellOn) then
# loop over 4 neighbors of (x,y) non := 0 ; for dx from -1 to 1 by 2 do for dy from -1 to 1 by 2 do # test of a neighbor nearer to origin if x^2+y^2 >= (x+dx)^2+(y+dy)^2 then if isOn(x+dx,y+dy,cellOn) then non := non+1 ; fi; fi; od: od: # exactly one neighbor on: add to nGen if non = 1 then nGen := [op(nGen), [x,y]] ; fi; fi; od: od: # merge old and new generation cellOn := [op(cellOn),op(nGen)] ; bbox := bb(cellOn) ; od: # R. J. Mathar, Jul 14 2009

A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (Function[pos, CellularAutomaton[{FromDigits[Boole[#[[2, 2]] == 1 || Count[Flatten[#], 1] == 1 && Count[Extract[#, pos], 1] == 1] & /@ Tuples[{1, 0}, {3, 3}], 2], 2, {1, 1}}, {{{1}}, 0}, {{{m}}, {-m, m}, {-m, m}}]] /@ Partition[{{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}, 2, 1, 1])], 2] (* JungHwan Min, Jan 23 2016 *)
A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (CellularAutomaton[{#, 2, {1, 1}}, {{{1}}, 0}, {{{m}}, {-m, m}, {-m, m}}] & /@ {13407603346151304507647333602124270744930157291580986197148043437687863763597662002711256755796972443613438635551055889478487182262900810351549134401372178, 13407603346151304507647333602124270744930157291580986197148043437687863763597777794800494071992396014598447323458909159463152822826940267935557047531012112, 13407603346151304507647333602124270744930157291580986197148043437687863763597777794800494071992396014598447323458909159463152822826940286382301121240563712, 13407603346151304507647333602124270744930157291580986197148043437687863763597662002711256755796972443613438635551055889478487182262900828798293208110923778})], 2] (* JungHwan Min, Jan 23 2016 *)
A160720[0]=0; A160720[n_]:=Total[With[{m = n - 1}, BitOr @@ (CellularAutomaton[{46, {2, ReplacePart[ArrayPad[{{1}}, 1], # -> 2]}, {1, 1}}, {{{1}}, 0}, {{{m}}, All, All}] & /@ Partition[{{-1, -1}, {-1, 1}, {1, 1}, {1, -1}}, 2, 1, 1])], 2] (* JungHwan Min, Jan 24 2016 *)

Conjecture: a(n) = 1 + 4*(A266532(n) - 1)/3, n >= 1. - Omar E. Pol, Jan 19 2016. This formula is correct! - N. J. A. Sloane, Jan 23 2016

a(n) = 1 + 4*A267700(n-1) = 1 + 2*(A159912(n) - n), n >= 1. - Omar E. Pol, Jan 24 2016

Edited by N. J. A. Sloane, Jun 26 2009

More terms from David Applegate, Jul 03 2009

A151920 a(n) = (Sum_{i=1..n+1} 3^wt(i))/3, where wt() = A000120().

Original entry on oeis.org

1, 2, 5, 6, 9, 12, 21, 22, 25, 28, 37, 40, 49, 58, 85, 86, 89, 92, 101, 104, 113, 122, 149, 152, 161, 170, 197, 206, 233, 260, 341, 342, 345, 348, 357, 360, 369, 378, 405, 408, 417, 426, 453, 462, 489, 516, 597, 600, 609, 618, 645, 654, 681, 708, 789, 798, 825, 852, 933, 960

Offset: 0

N. J. A. Sloane, Aug 05 2009, Aug 06 2009

Partial sums of A147610 (but with offset changed to 0).

It appears that the first bisection gives the positive terms of A147562. - Omar E. Pol, Mar 07 2015

			n=3: (3^1+3^1+3^2+3^1)/3 = 18/3 = 6.
n=18: the binary expansion of 18+1 is 10011, i.e., 19 = 2^4 + 2^1 + 2^0.
The exponents of these powers of 2 (4, 1 and 0) reoccur as exponents in the powers of 4: a(19) = 3^0 * [(4^4 - 1) / 3 + 1] + 3^1 * [(4^1 - 1) / 3 + 1] + 3^2 * [(4^0 - 1)/3 + 1] = 1 * 86 + 3 * 2 + 9 * 1 = 101. - _David A. Corneth_, Mar 21 2015

Michael De Vlieger, Table of n, a(n) for n = 0..10000
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, p. 31.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A000120, A130665, A147562, A147610, A153000, A160410, A160414.

Cf. A139250, A151917, A152998.

t = Nest[Join[#, # + 1] &, {0}, 14]; Table[Sum[3^t[[i + 1]], {i, 1, n}]/3, {n, 60}] (* Michael De Vlieger, Mar 21 2015 *)

a(n) = sum(i=1, n+1, 3^hammingweight(i))/3; \\ Michel Marcus, Mar 07 2015

a(n)={b=binary(n+1);t=#b;e=-1;sum(i=1,#b,e+=(b[i]==1);(b[i]==1)*3^e*((4^(#b-i)-1)/3+1))} \\ David A. Corneth, Mar 21 2015

a(n) = (A147562(n+2) - 1)/4 = (A151917(n+2) - 1)/2. - Omar E. Pol, Mar 13 2011
a(n) = (A130665(n+1) - 1)/3. - Omar E. Pol, Mar 07 2015
a(n) = a(n-1) + 3^A000120(n+1)/3. - David A. Corneth, Mar 21 2015

A161342 Number of "ON" cubic cells at n-th stage in simple 3-dimensional cellular automaton: a(n) = A160428(n)/8.

Original entry on oeis.org

0, 1, 8, 15, 64, 71, 120, 169, 512, 519, 568, 617, 960, 1009, 1352, 1695, 4096, 4103, 4152, 4201, 4544, 4593, 4936, 5279, 7680, 7729, 8072, 8415, 10816, 11159, 13560, 15961, 32768, 32775, 32824, 32873, 33216, 33265, 33608, 33951, 36352, 36401, 36744, 37087, 39488

Offset: 0

Omar E. Pol, Jun 14 2009

nonn

First differences are in A161343. - Omar E. Pol, May 03 2015
From Gary W. Adamson, Aug 30 2016: (Start)
Let M =
  1, 0, 0, 0, 0, ...
  8, 0, 0, 0, 0, ...
  7, 1, 0, 0, 0, ...
  0, 8, 0, 0, 0, ...
  0, 7, 1, 0, 0, ...
  0, 0, 8, 0, 0, ...
  0, 0, 7, 1, 0, ...
  ...
Then M^k converges to a single nonzero column giving the sequence.
The sequence with offset 1 divided by its aerated variant is (1, 8, 7, 0, 0, 0, ...). (End)

Alois P. Heinz, Table of n, a(n) for n = 0..16383
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A160410, A160428, A161343, A006046, A130665, A116520, A130667, A116522, A116526, A116525, A360189.

b:= proc(n) option remember; `if`(n<0, 0,
      b(n-1)+x^add(i, i=Bits[Split](n)))
    end:
a:= n-> subs(x=7, b(n-1)):
seq(a(n), n=0..44);  # Alois P. Heinz, Mar 06 2023

A161342list[nmax_]:=Join[{0},Accumulate[7^DigitCount[Range[0,nmax-1],2,1]]];A161342list[100] (* Paolo Xausa, Aug 05 2023 *)

From Nathaniel Johnston, Nov 13 2010: (Start)
a(n) = Sum_{k=0..n-1} 7^A000120(k).
a(n) = 1 + 7 * Sum_{k=1..n-1} A151785(k), for n >= 1.
a(2^n) = 2^(3n).
(End)
a(n) = Sum_{k=0..floor(log_2(n))} 7^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

More terms from Nathaniel Johnston, Nov 13 2010

A160412 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (see Comments for precise definition).

Original entry on oeis.org

0, 3, 12, 21, 48, 57, 84, 111, 192, 201, 228, 255, 336, 363, 444, 525, 768, 777, 804, 831, 912, 939, 1020, 1101, 1344, 1371, 1452, 1533, 1776, 1857, 2100, 2343, 3072, 3081, 3108, 3135, 3216, 3243, 3324, 3405, 3648, 3675, 3756, 3837, 4080, 4161, 4404, 4647

Offset: 0

Omar E. Pol, May 20 2009, Jun 01 2009

nonn

From Omar E. Pol, Nov 10 2009: (Start)
On the infinite square grid, consider the outside corner of an infinite square.
We start at round 0 with all cells in the OFF state.
The rule: A cell in turned ON iff exactly one of its four vertices is a corner vertex of the set of ON cells. So in each generation every exposed vertex turns on three new cells.
At round 1, we turn ON three cells around the corner of the infinite square, forming a concave-convex hexagon with three exposed vertices.
At round 2, we turn ON nine cells around the hexagon.
At round 3, we turn ON nine other cells. Three cells around of every corner of the hexagon.
And so on.
Shows a fractal-like behavior similar to the toothpick sequence A153006.
For the first differences see the entry A162349.
For more information see A160410, which is the main entry for this sequence.
(End)

			If we label the generations of cells turned ON by consecutive numbers we get the cell pattern shown below:
...77..77..77..77
...766667..766667
....6556....6556.
....654444444456.
...76643344334667
...77.43222234.77
......44211244...
00000000001244...
00000000002234.77
00000000004334667
0000000000444456.
0000000000..6556.
0000000000.766667
0000000000.77..77
0000000000.......
0000000000.......
0000000000.......

Michael De Vlieger, Table of n, a(n) for n = 0..1000
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.]
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, p. 31.
Omar E. Pol, Illustration of initial terms [From _Omar E. Pol_, Nov 10 2009]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata - _Omar E. Pol_, Nov 10 2009

Cf. A139250, A139251, A153006, A152980, A160410, A160414.

Cf. A130665, A162349. - Omar E. Pol, Nov 10 2009

a[n_] := 3*Sum[3^DigitCount[k, 2, 1], {k, 0, n - 1}]; Array[a, 48, 0] (* Michael De Vlieger, Nov 01 2022 *)

From Omar E. Pol, Nov 10 2009: (Start)
a(n) = A160410(n)*3/4.
a(0) = 0, a(n) = A130665(n-1)*3, for n>0.
(End)

More terms from Omar E. Pol, Nov 10 2009
Edited by Omar E. Pol, Nov 11 2009
More terms from Nathaniel Johnston, Nov 06 2010
More terms from Colin Barker, Apr 19 2015

cp's OEIS Frontend

A160414 Number of "ON" cells at n-th stage in simple 2-dimensional cellular automaton (same as A160410, but a(1) = 1, not 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A161411 First differences of A160410.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A160428 Number of ON cells at n-th stage of three-dimensional version of the cellular automaton A160410, using cubes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A160799 Partial sums of A160410.

Views

Author

Keywords

Crossrefs

Programs

PARI

Extensions

A147562 Number of "ON" cells at n-th stage in the "Ulam-Warburton" two-dimensional cellular automaton.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

Formula

Extensions

A160720 Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition).

Views

Author

Keywords

Comments