A360142 -id:A360142 - cp's OEIS frontend

A359303 Bitwise encoding of the state of a 1D cellular automaton after n steps from ...111000... where adjacent cells swap 01 <-> 10 when within triples 110 or 011.

1, 3, 5, 11, 13, 39, 43, 45, 103, 155, 171, 173, 359, 411, 619, 669, 1367, 1371, 1387, 1437, 3287, 4923, 5339, 5467, 5483, 5533, 11479, 13115, 19675, 21339, 21739, 21853, 43735, 43835, 44251, 45915, 52459, 78685, 170455, 173755, 174555, 174811, 174939, 175339, 176989, 367063, 419515, 629211

Offset: 1

Raphael J. F. Berger, Dec 25 2022

This automaton is a toy model for diffusion. It is inspired by the "Unstable Diffusion" problem encountered on day 23 of the "Advent of Code 2022" challenge and it serves as a 1D counterpart to the 2D cellular automaton featured there.
The state is a bi-infinite string of 1's and 0's of the form ...1111 middle 0000...
The state is encoded in an integer by discarding the left infinite 1's and one 0 which follows, then interpret the rest left-to-right as binary least- to most-significant bit.
The state steps by locating all cells which will swap, and applying those swaps simultaneously.
In pattern 110, the 10 cells swap to become 01, and conversely in pattern 011 the 01 cells swap to become 10.
Patterns can overlap so that, for example, 0110 is an 011 and a 110 and the two swaps step to 1001.
Swaps conflict in a pattern 11011 since they try to swap the 0 both to the left and to the right. When this happens, neither of these conflicting swaps are applied.
At least one swap always occurs since the rightmost 11 pair is followed by 0 and this 110 has no further 11 after which would conflict.
The total number of 1's and 0's is preserved in each state (when taking some large enough part of the bi-infinite state).

			For n=1, the starting state steps by a single swap, marked (), and the resulting string excluding left ...1110 is the bits of a(1) = 1,
  start      ...11110000...
                   ()
  a(1) = 1 = ...11101000...
                    \---> bits 100...
Conflicting swaps are seen at n=2 in pattern 11011. Its 101 is unchanged, but the right 11 is also part of a 110 and it does swap,
  a(2) = 3 = ...11110110000...
                   CCC()
  a(3) = 5 = ...11110101000...
                     \---> bits 101... = 5
Bit encoding direction, least- to most-significant, is seen at n=5,
  a(5) = 13 = ...1111010110000...
                      \--->  bits 1011
Overlapping swaps in pattern 0110 are seen at n=8,
  a(8) = 45 =   ...111101011010000...
                      () ()()
  a(9) = 103 = ...1111011100110000...

Raphael J. F. Berger, Table of n, a(n) for n = 1..1000
Kevin Ryde, PARI/GP Code
Eric Wastl, Advent of Code 2022, day 23

Cf. A360141, A360142, A030101, A035327, A053644.

ClearAll[{s,prop,checkprop,doprop,run,p,pa,a,j}];
prop[s_]:=(p=Array[0#&,Length[s]];
Do[If[i==1 ||i==Length[s],p[[i]]=0,
   {p[[i-1]],p[[i]],p[[i+1]]}+=
  Piecewise[{{{1,-1,0},{s[[i-1]],s[[i]],s[[i+1]]}=={0,1,1}},
                        {{0,-1,1},{s[[i-1]],s[[i]],s[[i+1]]}=={1,1,0}}},{0,0,0}]],{i,1,Length[s]-1} ];
                                  Return[p])
checkprop[s_]:=(p=s;
                                          Do[If[p[[i]]==2,{p[[i-1]],p[[i]],p[[i+1]]}={0,0,0}],{i,2,Length[s]-1}];
                                          Return[p])
doprop[s_]:= Return[s +checkprop[prop[s]]]
(* the cellular automaton starting with n+5 "1" cells and n+5 "0" cells *)
run[n_]:=( s=Join[Array[#/#&,n+5],Array[0#&,n+5]] ;Table[Nest[doprop[#]&,s,k],{k,0,n}])
(*conversion from the automaton states to integers *)
(* a[10] returns {1,3,5,11,13,39,43,45,103} *)
a[j_]:=Table[FromDigits[Reverse[run[j+1][[k,All]]/.{Longest[1 ...], x___} :> {x}],2]/2,{k,2,j+1}]

PARI
```
\\ See links.
```

a(n) = A030101(A035327(A360142(n))) + A360141(n) * A062383(A035327(A360142(n))), being reconstruction from left half (A360141) and right half (A360142). - Raphael J. F. Berger, Jun 21 2023

A360141 Bitwise encoding of the right half, initially empty, state of the 1D cellular automaton from A359303 after n steps.

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 9, 10, 10, 11, 12, 19, 20, 21, 21, 21, 22, 25, 38, 41, 42, 42, 43, 44, 51, 76, 83, 84, 85, 85, 85, 86, 89, 102, 153, 166, 169, 170, 170, 170, 171, 172, 179, 204, 307, 332, 339, 340, 341, 341, 341, 342, 345, 358, 409, 614, 665

Offset: 0

Raphael J. F. Berger, Jan 27 2023

See A359303 for how the automaton steps.
The automaton state is a bi-infinite string of 1's and 0's of the form ...1111 middle 0000... and the right half here is the part which began as 0's.
The right half state is encoded in an integer by interpreting the bits from left to right as binary from least to most significant bit.

			Following the state progression from A359303 (state(n)) is converted to the sequence (a(n)) by:
               state(0) =   ..1111|0000..
                                  |0000..
                       a(0) = 0 = \---> bits 000..
               state(1) =   ..1110|1000..
                                  |1000..
                       a(1) = 1 = \---> bits 100..
               state(2) = ..111101|10000..
                                  |10000..
                       a(2) = 1 = \---> bits 100..
               state(3) = ..111101|01000..
                                  |01000..
                       a(3) = 2 = \---> bits 01000..
               state(4) = ..111011|01000..
                       a(4) = 2 = \---> bits 01000..
               state(5) = ..111010|11000..
                       a(5) = 3 = \---> bits 11000..

Kevin Ryde, Table of n, a(n) for n = 0..3000
Kevin Ryde, PARI/GP Code

Cf. Base sequence A359303. Encoding of complementary left-half in A360142.

ClearAll[{s, prop, checkprop, doprop, p, a, j,runpos}];
prop[s_]:=(p=Array[0#&, Length[s]];
Do[If[i==1 ||i==Length[s], p[[i]]=0,
{p[[i-1]], p[[i]], p[[i+1]]}+=
Piecewise[{{{1, -1, 0}, {s[[i-1]], s[[i]], s[[i+1]]}=={0, 1, 1}},
{{0, -1, 1}, {s[[i-1]], s[[i]], s[[i+1]]}=={1, 1, 0}}}, {0, 0, 0}]], {i, 1, Length[s]-1} ];
Return[p])
checkprop[s_]:=(p=s;
Do[If[p[[i]]==2, {p[[i-1]], p[[i]], p[[i+1]]}={0, 0, 0}], {i, 2, Length[s]-1}];
Return[p])
doprop[s_]:= Return[s +checkprop[prop[s]]]
(* show only positive states: *)
runpos[n_]:=( s=Join[Array[#/#&, n+5], Array[0#&, n+5]] ; Table[Drop[Nest[doprop[#]&, s, k],n+5], {k, 0, n}])
(* conversion from the automaton states to integers *)
(* a[10] returns {0,1,1,2,2,3,4,5,5,6,9} *)
a[j_]:=Table[FromDigits[Reverse[runpos[j+1][[k, All]]],2], {k, 1, j+1}]

PARI
```
\\ See links.
```

cp's OEIS Frontend

A359303 Bitwise encoding of the state of a 1D cellular automaton after n steps from ...111000... where adjacent cells swap 01 <-> 10 when within triples 110 or 011.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula