A359303 - OEIS

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.

%I #96 Apr 01 2024 12:09:17

%S 1,3,5,11,13,39,43,45,103,155,171,173,359,411,619,669,1367,1371,1387,

%T 1437,3287,4923,5339,5467,5483,5533,11479,13115,19675,21339,21739,

%U 21853,43735,43835,44251,45915,52459,78685,170455,173755,174555,174811,174939,175339,176989,367063,419515,629211

%N 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.

%C 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.

%C The state is a bi-infinite string of 1's and 0's of the form ...1111 middle 0000...

%C 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.

%C The state steps by locating all cells which will swap, and applying those swaps simultaneously.

%C In pattern 110, the 10 cells swap to become 01, and conversely in pattern 011 the 01 cells swap to become 10.

%C Patterns can overlap so that, for example, 0110 is an 011 and a 110 and the two swaps step to 1001.

%C 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.

%C 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.

%C 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).

%H Raphael J. F. Berger, <a href="/A359303/b359303.txt">Table of n, a(n) for n = 1..1000</a>

%H Kevin Ryde, <a href="/A359303/a359303.gp.txt">PARI/GP Code</a>

%H Eric Wastl, <a href="https://adventofcode.com/2022/day/23">Advent of Code 2022, day 23</a>

%F 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

%e 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,

%e start ...11110000...

%e ()

%e a(1) = 1 = ...11101000...

%e \---> bits 100...

%e 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,

%e a(2) = 3 = ...11110110000...

%e CCC()

%e a(3) = 5 = ...11110101000...

%e \---> bits 101... = 5

%e Bit encoding direction, least- to most-significant, is seen at n=5,

%e a(5) = 13 = ...1111010110000...

%e \---> bits 1011

%e Overlapping swaps in pattern 0110 are seen at n=8,

%e a(8) = 45 = ...111101011010000...

%e () ()()

%e a(9) = 103 = ...1111011100110000...

%t ClearAll[{s,prop,checkprop,doprop,run,p,pa,a,j}];

%t prop[s_]:=(p=Array[0#&,Length[s]];

%t Do[If[i==1 ||i==Length[s],p[[i]]=0,

%t {p[[i-1]],p[[i]],p[[i+1]]}+=

%t Piecewise[{{{1,-1,0},{s[[i-1]],s[[i]],s[[i+1]]}=={0,1,1}},

%t {{0,-1,1},{s[[i-1]],s[[i]],s[[i+1]]}=={1,1,0}}},{0,0,0}]],{i,1,Length[s]-1} ];

%t Return[p])

%t checkprop[s_]:=(p=s;

%t Do[If[p[[i]]==2,{p[[i-1]],p[[i]],p[[i+1]]}={0,0,0}],{i,2,Length[s]-1}];

%t Return[p])

%t doprop[s_]:= Return[s +checkprop[prop[s]]]

%t (* the cellular automaton starting with n+5 "1" cells and n+5 "0" cells *)

%t run[n_]:=( s=Join[Array[#/#&,n+5],Array[0#&,n+5]] ;Table[Nest[doprop[#]&,s,k],{k,0,n}])

%t (*conversion from the automaton states to integers *)

%t (* a[10] returns {1,3,5,11,13,39,43,45,103} *)

%t a[j_]:=Table[FromDigits[Reverse[run[j+1][[k,All]]/.{Longest[1 ...], x___} :> {x}],2]/2,{k,2,j+1}]

%o (PARI) \\ See links.

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

%K nonn,easy

%O 1,2

%A _Raphael J. F. Berger_, Dec 25 2022