A266532 -id:A266532 - cp's OEIS frontend

A266533 First differences of A266532.

1, 3, 3, 9, 3, 9, 9, 21, 3, 9, 9, 21, 9, 21, 21, 45, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93, 9, 21, 21, 45, 21, 45, 45, 93, 21, 45, 45, 93, 45, 93, 93, 189, 3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93

Offset: 1

David Applegate and Omar E. Pol, Jan 18 2016

Number of Y-toothpicks added at n-th stage in the structure of A266532.

A simplified version of A160121.

			Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
1;
3;
3, 9;
3, 9, 9, 21;
3, 9, 9, 21, 9, 21, 21, 45;
3, 9, 9, 21, 9, 21, 21, 45, 9, 21, 21, 45, 21, 45, 45, 93;
...
Observation: at least the first 11 terms of the right border coincide with A068156.

David Applegate, The movie version
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. A000120, A011782, A038573, A068156. A139251, A147582, A160121, A151710, A160721, A266532, A267701.

a(1) = 1. It appears that a(n) = 3*A038573(n-1), n >= 2.

A267700 "Tree" sequence in a 90-degree sector of the cellular automaton of A160720.

Original entry on oeis.org

0, 1, 2, 5, 6, 9, 12, 19, 20, 23, 26, 33, 36, 43, 50, 65, 66, 69, 72, 79, 82, 89, 96, 111, 114, 121, 128, 143, 150, 165, 180, 211, 212, 215, 218, 225, 228, 235, 242, 257, 260, 267, 274, 289, 296, 311, 326, 357, 360, 367, 374, 389, 396, 411, 426, 457, 464, 479, 494, 525, 540, 571, 602, 665, 666, 669, 672, 679, 682, 689

Offset: 0

Omar E. Pol, Jan 19 2016

nonn

Conjecture: this is also the "tree" sequence in a 120-degree sector of the cellular automaton of A266532.
It appears that this is also the partial sums of A038573.
a(n) is also the total number of ON cells after n-th stage in the tree that arises from one of the four spokes in a 90-degree sector of the cellular automaton A160720 on the square grid.
Note that the structure of A160720 is also the "outward" version of the Ulam-Warburton cellular automaton of A147562.
It appears that A038573 gives the number of cells turned ON at n-th stage.
Conjecture: a(n) is also the total number of Y-toothpicks after n-th stage in the tree that arises from one of the three spokes in a 120-degree sector of the cellular automaton of A266532 on the triangular grid.
Note that the structure of A266532 is also the "outward" version of the Y-toothpick cellular automaton of A160120.
It appears that A038573 also gives the number of Y-toothpicks added at n-th stage.
Comment from N. J. A. Sloane, Jan 23 2016: All the above conjectures are true!
From Gus Wiseman, Mar 31 2019: (Start)
a(n) is also the number of nondecreasing binary-containment pairs of positive integers up to n. A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second. For example, the a(1) = 1 through a(6) = 12 pairs are:
  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)  (1,1)
         (2,2)  (1,3)  (1,3)  (1,3)  (1,3)
                (2,2)  (2,2)  (1,5)  (1,5)
                (2,3)  (2,3)  (2,2)  (2,2)
                (3,3)  (3,3)  (2,3)  (2,3)
                       (4,4)  (3,3)  (2,6)
                              (4,4)  (3,3)
                              (4,5)  (4,4)
                              (5,5)  (4,5)
                                     (4,6)
                                     (5,5)
                                     (6,6)
(End)

David Applegate, The movie version
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. A000120, A038573, A147562, A160120, A160720, A161336, A169779, A266532, A266534, A266536.
Cf. A006218, A019565, A070939, A080572, A267610, A267700.
Cf. A325101, A325103, A325104, A325106, A325109, A325110, A325124.

Accumulate[Table[2^DigitCount[n,2,1]-1,{n,0,30}]] (* based on conjecture confirmed by Sloane, Gus Wiseman, Mar 31 2019 *)

a(n) = (A160720(n+1) - 1)/4.
Conjecture 1: a(n) = (A266532(n+1) - 1)/3.
Conjecture 2: a(n) = A160720(n+1) - A266532(n+1).
All of the above conjectures are true. -  N. J. A. Sloane, Jan 23 2016
(Conjecture) a(n) = A267610(n) + n. - Gus Wiseman, Mar 31 2019

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

A159912 Partial sums of A159913(k) = 2^bitcount(2k+1)-1 = A038573(2k+1), bitcount=A000120.

Original entry on oeis.org

0, 1, 4, 7, 14, 17, 24, 31, 46, 49, 56, 63, 78, 85, 100, 115, 146, 149, 156, 163, 178, 185, 200, 215, 246, 253, 268, 283, 314, 329, 360, 391, 454, 457, 464, 471, 486, 493, 508, 523, 554, 561, 576, 591, 622, 637, 668, 699, 762, 769, 784, 799, 830, 845, 876, 907

Offset: 0

M. F. Hasler, May 03 2009

nonn

More precisely, a(n)=sum(iA159913(i)), since we want the sequence to start with a(0)=0 and not with A159913(0)=1.

a(n) is also the total number of ON cells after n generations in the outward corner version of the Ulam-Warburton cellular automaton of A147562, and a(n) is also the total number of Y-toothpicks after n generations in the outward corner version of the Y-toothpick structure of A160120. - David Applegate and Omar E. Pol, Jan 24 2016

Paolo Xausa, 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. 6, 30.
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. A000120, A038573, A147562, A159913, A160120, A160720, A266532, A267700.

Accumulate@ Table[2^(DigitCount[n, 2][[1]] + 1) - 1, {n, 0, 54}] (* Michael De Vlieger, Jan 25 2016 *)

PARI
```
A159912(n)=sum(i=0,n-1,1<
				
```

a(n) = sum( i=0...n-1, A159913(i)) = sum(i=0..n-1, 2^A000120(i))*2-n

a(n) = n + (A160720(n) - 1)/2 = n + 2*(A266532(n) - 1)/3 = n + 2*A267700(n-1), n >= 1. - Omar E. Pol, Jan 25 2016

A267701 a(n) = (A160121(n) - A266533(n))/6.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 4, 0, 0, 0, 1, 0, 0, 1, 4, 0, 1, 1, 5, 2, 4, 4, 13, 2, 0, 0, 1, 0, 1, 1, 4, 0, 1, 1, 5, 2, 4, 4, 13, 2, 1, 1, 5, 2, 5, 6, 16, 5, 4, 4, 15, 8, 13, 15, 38, 10, 0, 0, 1, 0, 1

Offset: 1

Omar E. Pol, Jan 19 2016

a(n) is 1/6 of the difference between the number of Y-toothpicks added at n-th stage in the structure of A160120 and the number of Y-toothpicks added at n-th stage stage in the structure of A266532 (the outward version of A160120).

			Written as an irregular triangle in which the row lengths are the terms of A011782 the sequence begins:
0;
0;
0,  0;
0,  0,0,0;
1,  0,0,0,1,0,1,1;
4,  0,0,0,1,0,0,1,4,0,1,1,5,2,4,4;
13, 2,0,0,1,0,1,1,4,0,1,1,5,2,4,4,13,2,1,1,5,2,5,6,16,5,4,4,15,8,13,15;
38,10,0,0,1,0,1...

Cf. A011782, A038573, A160120, A160121, A266532, A266533.

cp's OEIS Frontend

A266533 First differences of A266532.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A267700 "Tree" sequence in a 90-degree sector of the cellular automaton of A160720.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A159912 Partial sums of A159913(k) = 2^bitcount(2k+1)-1 = A038573(2k+1), bitcount=A000120.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A267701 a(n) = (A160121(n) - A266533(n))/6.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs