paper

Modulo Three Problem With A Cellular Automaton Solution

arXiv:nlin/0207032 · doi:10.1142/S0129183103004450

Abstract

An important global property of a bit string is the number of ones in it. It has been found that the parity (odd or even) of this number can be found by a sequence of deterministic, translational invariant cellular automata with parallel update in succession for a total of O(N^2) time. In this paper, we discover a way to check if this number is divisible by three using the same kind of cellular automata in O(N^3) time. We also speculate that the method described here could be generalized to check if it is divisible by four and other positive integers.

arXiv comment10 pages in revtex 4.0, using amsfonts

References in corpus (1)