# fCAtorization

I came up with a cellular automaton for factoring numbers. Fairly ironheaded and I’m sure not novel but a fun exercise for me. Here’s the Golly rules file. Yeah, there’s 13 states. I did say ironheaded.

In the initial state there are two cells on, one in state 1 (blue) at $(0, n)$ and one in state 2 (dark red) at $(n, n)$ (with $n>2$). Here’s $n = 12$:The CA starts building some infrastructure: a top axis ($y = n$) in dark red, a vertical axis ($x=0$) in blue, a bottom axis ($y = 0$) in light green, and a main diagonal ($y=x$) in dark green. The bottom axis is where results will be shown: after $3n-3$ generations, cell $(m,0)$ will be red if and only if $m$ is a factor of $n$ (for $0\leq m\leq n$).But in that picture the top and left axes and the main diagonal are only half finished, and there’s other stuff going on. What’s that? It’s already testing numbers to see if they’re factors. The infrastructure’s not complete but there’s enough there to get started.

Here the top and left axes and the main diagonal are completed, and the bottom axis is under way. On the right is a grey glider heading south, which will tell the bottom axis where to stop. And here the bottom axis is done, in time for a blue south-going glider to mark 6 as a factor. 1 is already marked as a factor: the regular CA mechanism won’t work for $m=1$, but it’s kind of safe to assume $1$ is a factor of $n$, so it’s marked as such immediately. So is $n$. Here the process is nearly finished. Four factors are marked:After 33 generations, action stops, with factors at 1, 2, 3, 4, 6, and 12 marked.It works as follows: For each $m$ from $n-1$ down to $2$, at the top axis a slow south-going (S) glider, with speed $c/2$ where $c$ means one cell per generation, and a SW-going glider with speed $c$ are dropped. When the SW glider hits the vertical axis it bounces off as an E glider (again speed $c$). After $2m$ generations the two gliders will collide, unless they hit the main diagonal first, in which case they’re deleted. If they collide before hitting the main diagonal the E glider bounces back SW, hits the vertical axis, and bounces back E for another potential collision after $4m$ generations. This continues, with the SW/E glider bouncing off the S glider and hitting the vertical axis at intervals of $m$ cells, until they collide with the main diagonal and are destroyed… or they collide with each other on the main diagonal. If that happens then obviously a bounce to the SW would send that glider to the origin, and that means $n$ (the length of the vertical axis) is evenly divisible by $m$. But instead of bouncing SW in that case, a new fast (speed $c$) S glider is dropped to the bottom axis, where it marks cell $m$ as a factor.

What’s tricky here is that this whole process is launched for $m-1$ one generation after it’s started for $m$! So a whole bunch of potential factors are being tested at any given time. It’s not obvious this can be made to work, especially since various SW and S gliders are launched cheek by jowl, and the slow S gliders are two cells wide. But it does work.

Here’s a couple videos: Testing $n=60$:

giving results 1, 2, 3, 4, 5, 10, 15, 20, 30, and 60, and testing $n=403$:

$403 = 13\times 31$, so there’s not much action on the bottom axis until just moments before the end.