A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata

Abstract: By using the methods of Rowland and Zeilberger (2014), we develop a meta-algorithm that, given a polynomial (in one or more variables), and a prime p, produces a fast (logarithmic time) algorithm that takes a positive integer n and outputs the number of times each residue class modulo p appears as a coecient when the polynomial is raised to the power n and the coecients are read modulo p. When p = 2, this has applications to counting the ON cells in certain \Odd-Rule " cellular automata. (This article is accompanied by a Maple package, CAcount, as well as numerous examples of input and output les, all of which can be obtained from the web page for this article