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.

%I A359303 #96 Apr 01 2024 12:09:17
%S A359303 1,3,5,11,13,39,43,45,103,155,171,173,359,411,619,669,1367,1371,1387,
%T A359303 1437,3287,4923,5339,5467,5483,5533,11479,13115,19675,21339,21739,
%U A359303 21853,43735,43835,44251,45915,52459,78685,170455,173755,174555,174811,174939,175339,176989,367063,419515,629211
%N 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.
%C A359303 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 A359303 The state is a bi-infinite string of 1's and 0's of the form ...1111 middle 0000...
%C A359303 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 A359303 The state steps by locating all cells which will swap, and applying those swaps simultaneously.
%C A359303 In pattern 110, the 10 cells swap to become 01, and conversely in pattern 011 the 01 cells swap to become 10.
%C A359303 Patterns can overlap so that, for example, 0110 is an 011 and a 110 and the two swaps step to 1001.
%C A359303 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 A359303 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 A359303 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 A359303 Raphael J. F. Berger, <a href="/A359303/b359303.txt">Table of n, a(n) for n = 1..1000</a>
%H A359303 Kevin Ryde, <a href="/A359303/a359303.gp.txt">PARI/GP Code</a>
%H A359303 Eric Wastl, <a href="https://adventofcode.com/2022/day/23">Advent of Code 2022, day 23</a>
%F A359303 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 A359303 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 A359303   start      ...11110000...
%e A359303                    ()
%e A359303   a(1) = 1 = ...11101000...
%e A359303                     \---> bits 100...
%e A359303 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 A359303   a(2) = 3 = ...11110110000...
%e A359303                    CCC()
%e A359303   a(3) = 5 = ...11110101000...
%e A359303                      \---> bits 101... = 5
%e A359303 Bit encoding direction, least- to most-significant, is seen at n=5,
%e A359303   a(5) = 13 = ...1111010110000...
%e A359303                       \--->  bits 1011
%e A359303 Overlapping swaps in pattern 0110 are seen at n=8,
%e A359303   a(8) = 45 =   ...111101011010000...
%e A359303                       () ()()
%e A359303   a(9) = 103 = ...1111011100110000...
%t A359303 ClearAll[{s,prop,checkprop,doprop,run,p,pa,a,j}];
%t A359303 prop[s_]:=(p=Array[0#&,Length[s]];
%t A359303 Do[If[i==1 ||i==Length[s],p[[i]]=0,
%t A359303    {p[[i-1]],p[[i]],p[[i+1]]}+=
%t A359303   Piecewise[{{{1,-1,0},{s[[i-1]],s[[i]],s[[i+1]]}=={0,1,1}},
%t A359303                         {{0,-1,1},{s[[i-1]],s[[i]],s[[i+1]]}=={1,1,0}}},{0,0,0}]],{i,1,Length[s]-1} ];
%t A359303                                   Return[p])
%t A359303 checkprop[s_]:=(p=s;
%t A359303                                           Do[If[p[[i]]==2,{p[[i-1]],p[[i]],p[[i+1]]}={0,0,0}],{i,2,Length[s]-1}];
%t A359303                                           Return[p])
%t A359303 doprop[s_]:= Return[s +checkprop[prop[s]]]
%t A359303 (* the cellular automaton starting with n+5 "1" cells and n+5 "0" cells *)
%t A359303 run[n_]:=( s=Join[Array[#/#&,n+5],Array[0#&,n+5]] ;Table[Nest[doprop[#]&,s,k],{k,0,n}])
%t A359303 (*conversion from the automaton states to integers *)
%t A359303 (* a[10] returns {1,3,5,11,13,39,43,45,103} *)
%t A359303 a[j_]:=Table[FromDigits[Reverse[run[j+1][[k,All]]/.{Longest[1 ...], x___} :> {x}],2]/2,{k,2,j+1}]
%o A359303 (PARI) \\ See links.
%Y A359303 Cf. A360141, A360142, A030101, A035327, A053644.
%K A359303 nonn,easy
%O A359303 1,2
%A A359303 _Raphael J. F. Berger_, Dec 25 2022