|
| |
|
|
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.
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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...
|
|
|
MATHEMATICA
|
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}]
|
|
|
PROG
|
(PARI) \\ See links.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
