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:Screen Shot 2015-11-06 at 10.48.46 AMThe 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).Screen Shot 2015-11-06 at 10.49.46 AMBut 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.Screen Shot 2015-11-06 at 10.50.33 AM 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.Screen Shot 2015-11-06 at 10.51.10 AM Here the process is nearly finished. Four factors are marked:Screen Shot 2015-11-06 at 10.51.45 AMAfter 33 generations, action stops, with factors at 1, 2, 3, 4, 6, and 12 marked.Screen Shot 2015-11-06 at 10.52.21 AMIt 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s