|
%I #61 Nov 02 2022 07:45:37
%S 0,1,5,9,21,25,37,49,77,81,93,105,133,145,173,201,261,265,277,289,317,
%T 329,357,385,445,457,485,513,573,601,661,721,845,849,861,873,901,913,
%U 941,969,1029,1041,1069,1097,1157,1185,1245,1305,1429,1441,1469,1497
%N Number of "ON" cells at n-th stage in 2-dimensional cellular automaton (see Comments for precise definition).
%C 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.
%C We start at stage 0 with all cells in OFF state.
%C At stage 1, we turn ON a single cell at the origin.
%C Once a cell is ON it stays ON.
%C 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.
%C 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.
%C This CA also arises as the cross-section in the (X,Y)-plane of the CA in A151776.
%C 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.
%C 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
%C 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
%H JungHwan Min, <a href="/A160720/b160720.txt">Table of n, a(n) for n = 0..5000</a>
%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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.]
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 30.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%F 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
%F a(n) = 1 + 4*A267700(n-1) = 1 + 2*(A159912(n) - n), n >= 1. - _Omar E. Pol_, Jan 24 2016
%e If we label the generations of cells turned ON by consecutive numbers we get the cell pattern shown below:
%e 9...............9
%e .8.8.8.8.8.8.8.8.
%e ..7...7...7...7..
%e .8.6.6.....6.6.8.
%e ....5.......5....
%e .8.6.4.4.4.4.6.8.
%e ..7...3...3...7..
%e .8...4.2.2.4...8.
%e ........1........
%e .8...4.2.2.4...8.
%e ..7...3...3...7..
%e .8.6.4.4.4.4.6.8.
%e ....5.......5....
%e .8.6.6.....6.6.8.
%e ..7...7...7...7..
%e .8.8.8.8.8.8.8.8.
%e 9...............9
%p 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
%p # 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
%t 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 *)
%t 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 *)
%t 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 *)
%Y Cf. A139250, A147562, A159912, A160117, A160118, A160120, A160721, A160740, A147562, A160410, A160414, A160412, A160416, A160796, A266532, A267700.
%K nonn
%O 0,3
%A _Omar E. Pol_, May 25 2009
%E Edited by _N. J. A. Sloane_, Jun 26 2009
%E More terms from _David Applegate_, Jul 03 2009
|
